3
$\begingroup$

Can this problem be solved in poly time?

Input: $S_i \subset \{1,\cdots,n\}$ for $i=1,\cdots, n$.

Question: Is it possible to select an $a_i \in S_i$ for each $i=1,\cdots,n$, such that $\{a_1,\cdots,a_n\}=\{1,\cdots,n\}$?

Informally, the problem asks for selecting one element from each subset $S_i$ such that the selected elements cover the set $\{1, \cdots, n\}$.

$\endgroup$
2
$\begingroup$

Hint: Form a bipartite graph which has the sets $S_1,\ldots,S_n$ on one side and the numbers $1,\ldots,n$ on the other. Connect $S_i$ to $a$ if $S_i$ contains $a$. You are looking for a perfect matching in this graph.

$\endgroup$

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.