2 ms·
No, it isn't. It is true that solving the Hamiltonian problem would solve Secret Santa. But the Secret Santa problem is more technically the "disjoint cycle p
by btilly 11y ago
No, it isn't. It is true that solving the Hamiltonian problem would solve Secret Santa. But the Secret Santa problem is more technically the "disjoint cycle problem" and that is in P.
See http://cstheory.stackexchange.com/questions/8563/partition-a-graph-into-node-disjoint-cycles http://cstheory.stackexchange.com/questions/8563/partition-a... for details.
- spooningtamarin 11y agoYeah, applying the algorithm can lead to sequences of transplant exchanges and save lives :D
- joe_the_user 11y agoWhile Hamiltonian Circuit is certainly harder, I don't think a Hamiltonian Circuit solver would be a Secret Santa Solver in all cases - two disjoint sets could have a Secret Santa solution but not a Hamiltonian graph solution.