2
$\begingroup$

Let $n,m$ be a positive integer with $m\ge 2n$. In the set $M=\{1,2,\dots,m\}$, some elements are black and others are white. Given $2n$ nonempty subsets of $M$, the task is to determine whether there exists a subset $T\subseteq M$ consisting of $n$ black and $n$ white elements such that each of the $2n$ subsets has a nonempty intersection with $T$. Can this be done in polynomial time?

Without the color constraint, this is very similar to the hitting set problem. Choosing a subset $T$ of size $2n$ without the color constraint is easy, by choosing one representative from each of the $2n$ subsets and, if the union of these representatives has size less than $2n$, fill in with arbitrary remaining elements of $M$. But having $n$ black and $n$ white elements is not always possible, for instance if there are not enough elements of one color.

$\endgroup$
1
  • $\begingroup$ It seems unlikely to me that this could be done in polynomial time, because you'd have to be able to answer correctly on instances with, e.g., exactly $n$ white elements that don't appear in any of the subsets, requiring us to hit the $2n$ subsets with exactly $n$ black elements. That doesn't quite reduce it to the fully-general hitting set problem, but it seems close enough to probably still be NP-hard. $\endgroup$ Mar 13 at 14:59
4
$\begingroup$

Can this be done in polynomial time?

No, it cannot (unless P equals NP, of course).

Consider the case where all the $2n$ sets only contain elements that are colored (say) black. Finding a "white-black hitting set" with $n$ pairs is now exactly the same as finding a regular hitting set with n elements. A reduction from Hitting Set

Find a set of at most $k$ elements that hits all sets in the collection $\mathcal{C}$, where $\mathcal{C} = r$

to your specific scenario

Find a set of $n$ pairs of white and black elements that hits all sets in the collection $\mathcal{C}$, where $|\mathcal{C}| = 2n$

follows easily. The only extra thing to take care of is if $2k < r$ (just add $r-2k$ black elements to $M$ and make each one a singleton set, now $n = r-k$), or if $2k > r$ (just take some arbitrary set $C\in \mathcal{C}$, add $2k-r$ extra elements to $M$ and, for each one make a set containing the union of it and $C$).

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.