Secret Santa is NP-Complete (2006) | Hacker News Reader

Secret Santa is NP-Complete (2006)

blogs.msdn.com

There's a common reasoning mistake when it comes to reduction and conclusion of complexity class. You cannot say a problem is NP-complete if you reduced it to an NP-complete problem.

The problem you know is NP-complete has to be reduced to your Santa problem.

What OP described was mapping from Secret Santa to Hamiltonian circuit, not the other way around.

I've had a bunch of problems reduced to be solvable with approximation algorithms of NP-hard problems, that doesn't make them NP-hard, it's equivalent to solving a problem by reducing it to an NP-complete one with an exponential algorithm.

That's why it's not that simple to prove a problem NP-complete.

It might be that the problem is filled with symmetry and by modifying an algorithm for an NP-complete problem you get a polynomial one.

For example, Vehicle Routing Problem with Time Windows (multiple Hamiltonians with time windows) is considered NP-hard but if your locations had a lot of short time windows you can solve any instance in polynomial time (almost O(n)). But you can also solve it with any VRPTW algorithm (DP, PTAS, heuristics etc.).

I don't think that's the mistake involved.

Rather, he simply (incorrectly as others have pointed out) asserts a 1-1 map between his problem and the Hamiltonian circuit problem. IE: "A Hamiltonian circuit is a path that traverses an entire graph by visting each node exactly one time. It turns out that this is exactly the problem I was trying to solve. " (exactly his problem equals, has a 1-1 map to Hamiltonian circuits).

Edit: his problem doesn't map either way to the Hamiltonian graph problem - you could have two disjoint graphs that could be solved as Secret Santa problems but not as Hamiltonian graph problems.

For the problem to be NP-Complete, it would have to be both in NP (the one thing that can be agreed on) and NP-hard. For it to be NP-hard, every problem in NP would have to be reducible to it. If we already know that the Hamiltonian circuit verification problem is NP-complete, and that the Secret Santa problem is NP, we de-facto know that S.S. is reducible to the Hamiltonian circuit. So the 'Aha' moment in the third to last paragraph is not new information.

It's true that if every NP problem were reducible to S.S., then it would be NP-hard, and as it can be verified in P time with the S.S. list and the list of people plus relations, and is thus in NP, it would also be NP-complete. It would also suffice to reduce an NP-complete problem to the S.S. problem as pictured here to prove NP-completeness.

But this article doesn't give proof of either and generally points in a different direction, like you said, so the title is really misleading and it would have been better to open the article with a question or discussion.

To summarize, this post by Rod Hilton is pretty useful in understanding the relation between P, NP, NP-hard, and NP-complete: http://www.nomachetejuggling.com/2012/09/14/traveling-salesm...

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... for details.

Yeah, applying the algorithm can lead to sequences of transplant exchanges and save lives :D

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.

We were just talking about this at the office this week and came to a similar conclusion. However, someone pointed out later that you could have a valid Secret Santa configuration that was not a Hamiltonian Path - you could have two (non-overlapping) paths and still have a valid secret santa: For people A B C D E F, you could have the graph covered by two separate circuits:

A->B->C->A

D->E->F->D

Unfortunately real-life intervened and we didn't have time to decide if this was an NP complete problem or not...

Well, you can always transform a true hamiltonian cycle to two cycles of a subgraph if you have a any A->B, C->D in the cycle where also A->D, B->C is in the graph. That's any 4 clique which isn't that hard, considering that the arrows can be transitive for that matter (I think, no proof attached).

Also, to show np completeness one must show reduction in both directions. I somehow doubt that any SAT-Problem is reducible to secret-santa, if secret santa isn't exactly hamiltonian cycle anyways.

Came to the same realisation - it's a vertex cycle cover, which can be found in polynomial time! (if one exists)

https://en.wikipedia.org/wiki/Vertex_cycle_cover

> It turns out that this is exactly the problem I was trying to solve. Imagine my Secret Santa problem as a graph where each person is a node and there are edges between all nodes that are not blacklisted. In this view of the problem, I'm trying to find a path around the graph, [visiting] each node once.

This is one of the fun things, to me, about having a background/interest in the more theoretical sides of CS/mathematics as a programmer. The day you realize that half the problems you're working on are really already solved (or related to) problems on graphs or some other structure, and if you reorganize your models around this you can get a much cleaner implementation. Come up with a representation of your problem using a graph, run a well-known algorithm from a graph library, solution found (hopefully before Christmas).

This is the one major gap I've noticed between professional programmers with a CS academic background versus those from an engineering academic background. The gap is easily closed, but the engineers lack the random bits of extra discrete maths or CS theory to make these kind of connections. OTOH, I'm sure programmers from an engineering background can easily say the same from the other side using some other set of knowledge.

The moral drawn from this particular case is a little less inspiring. The author was mistaken in drawing equivalence between his problem and the NP-complete one, and published a conclusion which was factually wrong. The mistake of equivalence is pointed out in the (years-old) comments, but no one knows whether it's significant.

Meanwhile, graph theory was aware of a polynomial-time solution to the guy's actual problem all along.

Some really sloppy thinking here. He didn't really define the problem he's trying to solve in the first place.

Here's how you do secret santa: take a list of people, shuffle the list, each person buys for the next person on the list, last person buys for the first person. Polynomial time.

Though, he is trying to solve a variation of secret santa which has blacklisted pairs, which means a random shuffle might result in an invalid ordering.

I took a stab at this exact scenario years ago (1999?) and came to roughly the same conclusion. I ultimately decided to treat it as a travelling salesman problem where the distances between nodes (people) were weighted based on how recently they had matched with each node in the past.

This ultimately led me to create a TSP solving library that implemented a bunch of the known heuristic algorithms to approximate the solution. Worked out pretty well in the end and learned lots while I was at it.

The real tricky part is making an algorithm that gives a uniformly random Secret Santa. In fact even generating a random permutation is quite tricky.

Usually the easiest is to just use Fisher-Yates to get a random permutation and reject it if it doesn't fit the criteria (people shouldn't pick themselves etc.). For nearly all practical problem sizes this should be fast enough.

Trying to reject permutation half way and fixing it has a tendency to cause subtle biases.

What's wrong with something like:

    generate a hash (e.g. md5) of current year (or 'draw' if you do secret santa
        once a month) and each person's name
    sort the people by their hashes
    draw 1 and 2 together, 3 and 4, etc.

"If there is a conflict with that person, slide to the next one on the list." "husband shouldn't draw wife's name, etc."

If there is a conflict with the last 2 people, you need to start over.

Reply on news.ycombinator.com