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.
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 &quot;white-black hitting set&quot; 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 &lt; r$ (just add $r-2k$ black elements to $M$ and make each one a singleton set, now $n = r-k$), or if $2k &gt; 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$).