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?


1 Answer 1


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$.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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