2
$\begingroup$

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.

$\endgroup$

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.