I'm wondering if the following problem is (or has been proven to be) NP-Complete.

Input: integer $n\ge0$, set $S_1,S_2,\ldots,S_{2n}$, set $T_1,T_2,\ldots,T_n$.

Accept iff: there exists $\{a_i,b_i\},i=1,2,\ldots,n$ such that $\{a_1,\ldots,a_n,b_1,\ldots,b_n\}=\{1,2,\ldots,2n\}$ and $S_{a_i}\cup S_{b_i}=T_i,S_{a_i}\cap S_{b_i}=\emptyset$.

That is, we want to partition $\{S_i\}$ as $n$ group of two sets, and the $i$-th group exactly covers $T_i$.

Towards algorithm, we can construct a colored graph with vertex set $\{v_1,\ldots,v_{2n}\}$ and $v_i,v_j$ is connected with color $k$ iff $S_i\cup S_j=T_k,S_i\cap S_j=\emptyset$. Then the problem asks for a perfect matching of distinct color.

I suspect the problem was considered before; or there is some other problem closely related. But all I can find is the comment in this problem.


Your Answer

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

Browse other questions tagged or ask your own question.