Two-color hitting set
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$).