# Two-color hitting set

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.

• 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. Mar 13 at 14:59

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$$

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$$).