patternMinor
Is the following NP-complete?
Viewed 0 times
followingcompletethe
Problem
I have encountered the following problem.
We have $N$ points in discrete coordinates,distributed through a plane with vertical axis $[1..Y]$ and horizontal axis $[1..X]$.
We can perform the action of removing all points with vertical coordinate $y$, in short removing $y$.
What is the least number of $y$'$s$ we must remove so that the number of $x$ that have points is less than $X/2$.
For example in the graph above removing 1 and 2 leaves points only in 1,3,6,9.
This seems like a NP-complete problem to me so the only solution I have developed is removing all combinations of $y'$s. I would be grateful if someone experienced in computation-theory could point me to a similar known problem (or maybe a problem this could be reduced to), any suggestion is welcome.
We have $N$ points in discrete coordinates,distributed through a plane with vertical axis $[1..Y]$ and horizontal axis $[1..X]$.
We can perform the action of removing all points with vertical coordinate $y$, in short removing $y$.
What is the least number of $y$'$s$ we must remove so that the number of $x$ that have points is less than $X/2$.
For example in the graph above removing 1 and 2 leaves points only in 1,3,6,9.
This seems like a NP-complete problem to me so the only solution I have developed is removing all combinations of $y'$s. I would be grateful if someone experienced in computation-theory could point me to a similar known problem (or maybe a problem this could be reduced to), any suggestion is welcome.
Solution
If you mean by "the number of $x$ that have points" that the number of distinct values $x$ such that there is a point $(x, y)$ such that $y$ has not been removed is at most $X/2$, then your problem is extremely similar to Set Cover, which is $\mathbf{NP}$-complete.
Your problem would be the variant in which you ask for the minimum number of sets needed to cover half the elements of your universe. I would be very surprised if this was not $\mathbf{NP}$-complete. I'll think about it some more and update this if I think up a proof of $\mathbf{NP}$-completeness.
Your problem would be the variant in which you ask for the minimum number of sets needed to cover half the elements of your universe. I would be very surprised if this was not $\mathbf{NP}$-complete. I'll think about it some more and update this if I think up a proof of $\mathbf{NP}$-completeness.
Context
StackExchange Computer Science Q#6542, answer score: 3
Revisions (0)
No revisions yet.