Let $n$ be a positive integer and $[n] := \{1,2,3,...,n\}$. You are given $k$ non-empty subsets of $[n]$. Decide whether it is possible to select exactly one element from each subset such that the elements selected form a permutation of $[n]$. I try to reduce the Hamiltonian cycle problem. However, Hamiltonian cycles only allow one cycle while permutations might have many cycles. How, please?
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
It is currently unknown whether your problem is NP-Hard. However, if it were, then it would be the case that P=NP.
To solve the problem in polynomial-time you can check whether a maximum matching in the following bipartite graph $G=(U \cup V, E)$ has size $n$:
- The set $U$ is $u_1, \dots, u_n$.
- The set $V$ is $v_1, \dots, v_k$.
- $(u_i, v_j) \in E$ if and only if the $j$-th subset contains $i$.
