Re:Secret Santa is NP-Complete (2006)
by joe_the_user on Friday December 11, 2015 @04:57PM
(#10720385)
While 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.
Re:Secret Santa is NP-Complete (2006)
by spooningtamarin on Friday December 11, 2015 @03:25PM
(#10719703)
Yeah, applying the algorithm can lead to sequences of transplant exchanges and save lives :D
See http://cstheory.stackexchange.com/questions/8563/partition-a... for details.