Secret Santa is NP-Completehttp://blogs.msdn.com/b/steverowe/archive/2006/12/19/secret-santa-is-np-complete.aspxEvery year my group of friends undertakes a Secret Santa gift exchange. When we started we each drew names from a hat and bought a gift for the names we drew. Being budding programmers, we soon dispensed with the hat and wrote a program to do the worken-USTelligent Evolution Platform Developer Build (Build: 5.6.50428.7875)re: Secret Santa is NP-Completehttp://blogs.msdn.com/b/steverowe/archive/2006/12/19/secret-santa-is-np-complete.aspx#1508970Mon, 22 Jan 2007 20:49:52 GMT91d46819-8472-40ad-a661-2c78acb4018c:1508970SteveRowe<p>There is another difficulty with "pass the hat" model. That is, it doesn't allow for blacklists. If you are doing a secret santa exchange with a bunch of unrelated people (a work group, a class of kids), this isn't a problem. However, if you are doing it in a group where there are families (brother/sister, husband/wife, etc.) then you really don't want a husband getting his wife for the exchange. The chances are pretty strong that he's getting her a gift elsewhere anyway. At this point, you need to pull a name from the hat and make sure it isn't on someone's list. If it is, throw it back and draw another. In a well connnected graph this still mostly works, but at the constraints increase, there is greater and greater likelihood that toward the end you'll get into a situation where the person drawing the name is blacklisted off of everyone left in the hat. Oops. Time to start over or do some serious backtracking.</p>
<div style="clear:both;"></div><img src="http://blogs.msdn.com/aggbug.aspx?PostID=1508970" width="1" height="1">re: Secret Santa is NP-Completehttp://blogs.msdn.com/b/steverowe/archive/2006/12/19/secret-santa-is-np-complete.aspx#1494418Fri, 19 Jan 2007 23:04:28 GMT91d46819-8472-40ad-a661-2c78acb4018c:1494418Maurits [MSFT]<p>Exanding audience...</p>
<p><a rel="nofollow" target="_new" href="http://channel9.msdn.com/ShowPost.aspx?PostID=273941#273941">http://channel9.msdn.com/ShowPost.aspx?PostID=273941#273941</a></p>
<div style="clear:both;"></div><img src="http://blogs.msdn.com/aggbug.aspx?PostID=1494418" width="1" height="1">re: Secret Santa is NP-Completehttp://blogs.msdn.com/b/steverowe/archive/2006/12/19/secret-santa-is-np-complete.aspx#1494352Fri, 19 Jan 2007 22:33:42 GMT91d46819-8472-40ad-a661-2c78acb4018c:1494352Maurits [MSFT]<p>Eugen's "no two-cycles" constraint is interesting. That breaks the analogy with drawing names out of a hat. I can't immediately decide whether adding this constraint makes the problem NP-complete.</p>
<div style="clear:both;"></div><img src="http://blogs.msdn.com/aggbug.aspx?PostID=1494352" width="1" height="1">re: Secret Santa is NP-Completehttp://blogs.msdn.com/b/steverowe/archive/2006/12/19/secret-santa-is-np-complete.aspx#1494327Fri, 19 Jan 2007 22:23:47 GMT91d46819-8472-40ad-a661-2c78acb4018c:1494327Maurits [MSFT]<p>I think Eugen is referring to the implementation most used by non-programmers -- to wit, pulling names out of a hat. This results, not in a Hamiltonian circuit, but in a series of cycles. You might get lucky and get one big cycle, but the probability is very large that you will have at least two.</p>
<p>It is fairly trivial to write a computer program that follows this implementation. It's certainly not NP-complete.</p>
<p>There are several problems with this, though.</p>
<p>1) Someone might draw their own name from the hat. This is typically worked-around by having them simply draw another name.</p>
<p>2) The very last person might draw their own name from the hat. This is typically worked-around by having someone in authority look at the last two names in the hat, and hand them out manually to the last two people.</p>
<p>3) The worst problem, though, is this makes the payoff inelegant. It's traditional for the unwrapping of Secret Santa presents to be in a particular order, along the "found" paths in the graph. Something like:</p>
<p>Alice opens the present with "To Alice" on it. "Wow!" she says, "a left-handed corkscrew!" After some gushing, John reveals himself to be Alice's Secret Santa.</p>
<p>Now it's *John*'s turn. John opens the present with "To John" on it. "Wow!" he says, "a dehumidifier!" After some gushing, Eric reveals himself to be ...</p>
<p>... and so on up the chain.</p>
<p>If you have a single Hamiltonian cycle, this works out great. Alice is the last person's Secret Santa.</p>
<p>If you have multiple cycles in the graph, you get to a sticking point. Fred opens the "To Fred" gift. "Wow!" he exclaims, "Season tickets to Husky volleyball!" After some gushing, *Alice* reveals herself to be Fred's Secret Santa.</p>
<p>At this point, there's an impasse. There are people left that haven't opened gifts... and there are unopened gifts... but *who gets to go?*</p>
<p>The tie is broken somehow, and the next cycle is traversed.</p>
<div style="clear:both;"></div><img src="http://blogs.msdn.com/aggbug.aspx?PostID=1494327" width="1" height="1">re: Secret Santa is NP-Completehttp://blogs.msdn.com/b/steverowe/archive/2006/12/19/secret-santa-is-np-complete.aspx#1490718Fri, 19 Jan 2007 01:35:56 GMT91d46819-8472-40ad-a661-2c78acb4018c:1490718SteveRowe<p>Interesting observation Eugen. It is certainly possible for a secret santa problem to be solved by creating subgraphs, each of which is a hamiltonian circuit. While this makes the n in O(2^n) a smaller n, each subgraph is still trying to create a hamiltonian circuit. I'm not sure how much this make it a non-NP problem. It also seems to introduce new choke points into the algorithm. If I arbitrarily break the graph into some smaller number of sets, how do I know that these sets will match and if they don't? If they don't, I'm back to my initial problem of a Hamiltonian circuit.</p>
<p>It's also possible that the graph isn't fully connected. I think this would have to be taken into account by an algorithm before we tried to find a hamiltonian circuit for it.</p>
<div style="clear:both;"></div><img src="http://blogs.msdn.com/aggbug.aspx?PostID=1490718" width="1" height="1">re: Secret Santa is NP-Completehttp://blogs.msdn.com/b/steverowe/archive/2006/12/19/secret-santa-is-np-complete.aspx#1489021Thu, 18 Jan 2007 19:20:25 GMT91d46819-8472-40ad-a661-2c78acb4018c:1489021Eugen Buehler<p>I'm not sure that the reduction of the Secret Santa problem to the Hamiltonian Circuit problem is valid. While it is true that a solution to the Hamiltonian Circuit problem would solve the Secret Santa problem, I think there are valid solutions to the Secret Santa problem that would not be encoded by a Hamiltonian circuit. Take the simple case of four people (A,B,C and D) with no constraints. The solution A->B,B->C,C->D,D->A would solve the problem and be a Hamiltonian Circuit. But A->B,B->A,C->D,D->C would be a valid Secret Santa solution but not a Hamiltonian Circuit. Even if we want to restrict things so that people don't have each other as Secret Santas, for six people we would have the solution A->B,B->C,C->A,D->E,E->F,F->D. Or am I missing something?</p>
<div style="clear:both;"></div><img src="http://blogs.msdn.com/aggbug.aspx?PostID=1489021" width="1" height="1">re: Secret Santa is NP-Completehttp://blogs.msdn.com/b/steverowe/archive/2006/12/19/secret-santa-is-np-complete.aspx#1343129Fri, 22 Dec 2006 02:10:21 GMT91d46819-8472-40ad-a661-2c78acb4018c:1343129Maurits [MSFT]<p>Oh, and here's a C++ implementation of the solution that works for Dirac graphs (each vertex has degree at least n/2:)</p>
<p><a rel="nofollow" target="_new" href="http://www.geocities.com/dharwadker/hamilton/main.html">http://www.geocities.com/dharwadker/hamilton/main.html</a></p>
<p>(section 6 - hamilton.cpp)</p>
<div style="clear:both;"></div><img src="http://blogs.msdn.com/aggbug.aspx?PostID=1343129" width="1" height="1">re: Secret Santa is NP-Completehttp://blogs.msdn.com/b/steverowe/archive/2006/12/19/secret-santa-is-np-complete.aspx#1342922Fri, 22 Dec 2006 01:57:41 GMT91d46819-8472-40ad-a661-2c78acb4018c:1342922Maurits [MSFT]<p>> I would not be surprised if there was a polynomial algorithm for finding a Hamiltonian circuit given a high enough edge density.</p>
<p>Bingo!</p>
<p><a rel="nofollow" target="_new" href="http://web.cs.wpi.edu/~gsarkozy/Cikkek/32.pdf">http://web.cs.wpi.edu/~gsarkozy/Cikkek/32.pdf</a></p>
<p>... which is a generalization of...</p>
<p><a rel="nofollow" target="_new" href="http://citeseer.ist.psu.edu/dahlhaus93parallel.html">http://citeseer.ist.psu.edu/dahlhaus93parallel.html</a></p>
<p>So if you can guarantee that</p>
<p>1) the blacklist is symmetric</p>
<p>AND</p>
<p>2) any individual person is eligible to give/receive from at least half of the remaining people</p>
<p>... then there's a polynomial algorithm.</p>
<p>See the Find_Hamiltonian_Circuit problem in the .pdf above.</p>
<p>If your blacklist is more intense than this... well... the brute force algorithm works, it's just a little slow.</p>
<p>It's also much easier to implement, I would think...</p>
<p>If you're a zombiemaster with unlimited computing power, this is the kind of NP-complete problem that lends itself well to parallelizability, since it reduces into independent components. You could find (n-1) slaves and give each of them one of the following tasks:</p>
<p>1) Find the solution given P1 -> P2</p>
<p>2) Find the solution given P1 -> P3</p>
<p>...</p>
<p>n-1) Find the solution given P1 -> Pn-1</p>
<p>These slaves could each, in turn, recruit (n-2) subslaves and parcel the task out one chain deeper. Eventually, one of the slaves' slaves' slaves' slaves' ... slaves finds the solution and reports back up the chain; each superior can then instruct its other subordinates to cease processing.</p>
<p>In the ultimate example of cheap parallel power, I was fortunate enough to be a student of Leonard Adleman when he solved a seven-node Hamiltonian path problem using DNA molecules:</p>
<p><a rel="nofollow" target="_new" href="http://en.wikipedia.org/wiki/Leonard_Adleman">http://en.wikipedia.org/wiki/Leonard_Adleman</a></p>
<div style="clear:both;"></div><img src="http://blogs.msdn.com/aggbug.aspx?PostID=1342922" width="1" height="1">re: Secret Santa is NP-Completehttp://blogs.msdn.com/b/steverowe/archive/2006/12/19/secret-santa-is-np-complete.aspx#1342622Fri, 22 Dec 2006 01:13:09 GMT91d46819-8472-40ad-a661-2c78acb4018c:1342622Maurits [MSFT]<p>Indeed, blacklisting is the heart and soul of the problem.</p>
<p>If there is no blacklist then the mathematical problem is "Find a Hamiltonian circuit through the *complete* graph on n vertices" - as you note, this is trivially solved by listing the vertices in whatever order you see fit.</p>
<p>If the blacklist is so intense that each person is only willing to deal with two other people, then the mathematical problem is "Find a Hamiltonian circuit through a graph G, all of whose vertices have degree 2" - this is also trivial. I was mistaken in my initial statement that all such graphs are circles; you could also have disconnected graphs with several circles.</p>
<p>If the blacklist is symmetric* and without any other internal structure, then you have a restatement of the general Hamiltonian circuit problem on an undirected graph, which is NP-complete and the brute-force solution is as good as you can get. A good implementation of the brute-force algorithm should be able to step through the various combinations in polynomial memory, and only take exponential time for very severe blacklists. I would not be surprised if there was a polynomial algorithm for finding a Hamiltonian circuit given a high enough edge density.</p>
<p>If there is hope in finding a wholly polynomial algorithm, it lies in finding an internal structure to the blacklist. </p>
<p>Your example blacklist entry is encouraging: "husband shouldn't draw wife's name".</p>
<p>Other sample blacklist entries: "person shouldn't draw the same name they drew last year."</p>
<p>If the blacklist entries can be standardized, the possibility of a polynomial algorithm that leverages the structure materializes. For example, the nodes could be structured into families, and the rule "members of a family cannot draw each other" formalized; this allows analysis impossible in the general case. In particular, if one family is bigger than all the others put together, no perfect Secret Santa chain exists.</p>
<p>If the set of people is the same for two years running, and the blacklist is symmetric*, a trivial (if rather lame) solution is simply to reverse the chain from the previous year; give to the person who gave to you. This violates the "Secret" condition, though, so I'll make it explicit: "person shouldn't know, or be able to deduce, who their Secret Santa is; nor who anyone else's Secret Santa is, with the exception of the person whose name they draw." This is the source of the need for randomization.</p>
<p>* By which I mean there are no one-way entries... for example, if Alice can give to Bob, but Bob is restricted from giving to Alice, then the analogy to the general Hamiltonian problem is broken.</p>
<div style="clear:both;"></div><img src="http://blogs.msdn.com/aggbug.aspx?PostID=1342622" width="1" height="1">re: Secret Santa is NP-Completehttp://blogs.msdn.com/b/steverowe/archive/2006/12/19/secret-santa-is-np-complete.aspx#1342221Fri, 22 Dec 2006 00:13:57 GMT91d46819-8472-40ad-a661-2c78acb4018c:1342221SteveRowe<p>A blacklist makes creating a graph with all vertexes degree 2 very difficult. Likewise, it would make the "create a list an shuffle it" hard too. At least, it would unless I'm misunderstanding it. If you have a bunch of names with no constraints then you can just assign each randomly to a position in the chain and come up with a solution but once you have blacklists, things become much harder.</p>
<p>From some initial reading it appears that the are heuristics that can be applied which sometimes work and some backtracking methods which will help to constrain the searches. It's still a difficult problem, but not quite as intractable.</p>
<div style="clear:both;"></div><img src="http://blogs.msdn.com/aggbug.aspx?PostID=1342221" width="1" height="1">re: Secret Santa is NP-Completehttp://blogs.msdn.com/b/steverowe/archive/2006/12/19/secret-santa-is-np-complete.aspx#1328048Wed, 20 Dec 2006 06:45:46 GMT91d46819-8472-40ad-a661-2c78acb4018c:1328048Max Battcher<p>As Maurits said, if you simplify your search space you can very easily get to a quicker deterministic algorithm.</p>
<p>The easiest way is to constrain to a "Secret Santa circle" in that each 0 -> 1 -> 2 -> 0. In this case it's simply a matter of shuffle the list of people and iterate through giving each the next person in the list. Pick a shuffle algorithm of your choice (Knuth's is O(n)) and the iteration is O(n).</p>
<p>Blacklists obviously complicate things, but under the above constraints shouldn't be too complex.</p>
<div style="clear:both;"></div><img src="http://blogs.msdn.com/aggbug.aspx?PostID=1328048" width="1" height="1">re: Secret Santa is NP-Completehttp://blogs.msdn.com/b/steverowe/archive/2006/12/19/secret-santa-is-np-complete.aspx#1326930Tue, 19 Dec 2006 21:21:59 GMT91d46819-8472-40ad-a661-2c78acb4018c:1326930Maurits [MSFT]<p>The Hamiltonian circuit problem is only NP-complete for general graphs. If you restrict the kinds of graphs that you consider, the problem may be become tractable.</p>
<p>For example, if you restrict the graphs to ones where every vertex has degree 2 (circles), the Hamiltonian circuit problem is trivial.</p>
<p>I wonder if there is a way to add reasonable constraints to the Secret Santa problem that allows for an elegant solution?</p>
<p>Of course, the brute-force solution also has its charms...</p>
<p>Given a set P of people P1, P2, P3... Pn;</p>
<p>And a set E of disallowable edges E1 = P1a -> P1b, E2 = P2a -> P2b, ... Em = Pma -> Pmb;</p>
<p>Find a Secret Santa cycle Pi1 -> Pi2 -> ... Pin -> Pi1 so that none of the edges of the set are disallowed;</p>
<p>Algorithm: construct the set of all permutations of P that start with P1 -- this is a set of size (n-1)!</p>
<p>Construct an enumerator to iterate through this set, starting with P1 -> P2 -> P3 ... -> Pn, and ending with P1 -> Pn -> Pn-1 -> ... P1</p>
<p>For each permutation, determine by inspection whether it contains any forbidden edges. If not, use this as the solution.</p>
<p>It may be objected that there is no randomization in this algorithm. This is true as far as it goes. I considered various methods of introducing randomness, and decided the simplest method would be to randomize the initial assignment of the Pi subscripts to the individual names.</p>
<div style="clear:both;"></div><img src="http://blogs.msdn.com/aggbug.aspx?PostID=1326930" width="1" height="1">