tag:blogger.com,1999:blog-736810000699453506.post4979784948776370978..comments2023-05-11T00:49:36.314-07:00Comments on Ruminations on Computing: Secret Santa is NP-CompleteSteve Rowehttp://www.blogger.com/profile/17905356014908630180noreply@blogger.comBlogger12125tag:blogger.com,1999:blog-736810000699453506.post-4319878905582811442006-12-19T05:21:59.000-08:002006-12-19T05:21:59.000-08:00The Hamiltonian circuit problem is only NP-complet...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.<br>For example, if you restrict the graphs to ones where every vertex has degree 2 (circles), the Hamiltonian circuit problem is trivial.<br>I wonder if there is a way to add reasonable constraints to the Secret Santa problem that allows for an elegant solution?<br>Of course, the brute-force solution also has its charms...<br>Given a set P of people P1, P2, P3... Pn;<br>And a set E of disallowable edges E1 = P1a -> P1b, E2 = P2a -> P2b, ... Em = Pma -> Pmb;<br>Find a Secret Santa cycle Pi1 -> Pi2 -> ... Pin -> Pi1 so that none of the edges of the set are disallowed;<br>Algorithm: construct the set of all permutations of P that start with P1 -- this is a set of size (n-1)!<br>Construct an enumerator to iterate through this set, starting with P1 -> P2 -> P3 ... -> Pn, and ending with P1 -> Pn -> Pn-1 -> ... P1<br>For each permutation, determine by inspection whether it contains any forbidden edges. If not, use this as the solution.<br>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.Mauritsnoreply@blogger.comtag:blogger.com,1999:blog-736810000699453506.post-208388662461243902006-12-19T14:45:46.000-08:002006-12-19T14:45:46.000-08:00As Maurits said, if you simplify your search space...As Maurits said, if you simplify your search space you can very easily get to a quicker deterministic algorithm.<br>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).<br>Blacklists obviously complicate things, but under the above constraints shouldn't be too complex.Max Battcherhttp://www.worldmaker.net/noreply@blogger.comtag:blogger.com,1999:blog-736810000699453506.post-38264724438587288282006-12-21T08:13:57.000-08:002006-12-21T08:13:57.000-08:00A blacklist makes creating a graph with all vertex...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.<br>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.SteveRowenoreply@blogger.comtag:blogger.com,1999:blog-736810000699453506.post-35848574022051681612006-12-21T09:13:09.000-08:002006-12-21T09:13:09.000-08:00Indeed, blacklisting is the heart and soul of the ...Indeed, blacklisting is the heart and soul of the problem.<br>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.<br>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.<br>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.<br>If there is hope in finding a wholly polynomial algorithm, it lies in finding an internal structure to the blacklist. <br>Your example blacklist entry is encouraging: "husband shouldn't draw wife's name".<br>Other sample blacklist entries: "person shouldn't draw the same name they drew last year."<br>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.<br>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.<br>* 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.Mauritsnoreply@blogger.comtag:blogger.com,1999:blog-736810000699453506.post-77121306313339044062006-12-21T09:57:41.000-08:002006-12-21T09:57:41.000-08:00> I would not be surprised if there was a polyn...> I would not be surprised if there was a polynomial algorithm for finding a Hamiltonian circuit given a high enough edge density.<br>Bingo!<br>http://web.cs.wpi.edu/~gsarkozy/Cikkek/32.pdf<br>... which is a generalization of...<br>http://citeseer.ist.psu.edu/dahlhaus93parallel.html<br>So if you can guarantee that<br>1) the blacklist is symmetric<br>AND<br>2) any individual person is eligible to give/receive from at least half of the remaining people<br>... then there's a polynomial algorithm.<br>See the Find_Hamiltonian_Circuit problem in the .pdf above.<br>If your blacklist is more intense than this... well... the brute force algorithm works, it's just a little slow.<br>It's also much easier to implement, I would think...<br>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:<br>1) Find the solution given P1 -> P2<br>2) Find the solution given P1 -> P3<br>...<br>n-1) Find the solution given P1 -> Pn-1<br>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.<br>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:<br>http://en.wikipedia.org/wiki/Leonard_AdlemanMauritsnoreply@blogger.comtag:blogger.com,1999:blog-736810000699453506.post-76166431633971991182006-12-21T10:10:21.000-08:002006-12-21T10:10:21.000-08:00Oh, and here's a C++ implementation of the sol...Oh, and here's a C++ implementation of the solution that works for Dirac graphs (each vertex has degree at least n/2:)<br>http://www.geocities.com/dharwadker/hamilton/main.html<br>(section 6 - hamilton.cpp)Mauritsnoreply@blogger.comtag:blogger.com,1999:blog-736810000699453506.post-47566028018289564252007-01-18T03:20:25.000-08:002007-01-18T03:20:25.000-08:00I'm not sure that the reduction of the Secret ...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?Eugen Buehlernoreply@blogger.comtag:blogger.com,1999:blog-736810000699453506.post-39623964642027836242007-01-18T09:35:56.000-08:002007-01-18T09:35:56.000-08:00Interesting observation Eugen. It is certainly po...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.<br>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.SteveRowenoreply@blogger.comtag:blogger.com,1999:blog-736810000699453506.post-10012931002301610262007-01-19T06:23:47.000-08:002007-01-19T06:23:47.000-08:00I think Eugen is referring to the implementation m...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.<br>It is fairly trivial to write a computer program that follows this implementation. It's certainly not NP-complete.<br>There are several problems with this, though.<br>1) Someone might draw their own name from the hat. This is typically worked-around by having them simply draw another name.<br>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.<br>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:<br>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.<br>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 ...<br>... and so on up the chain.<br>If you have a single Hamiltonian cycle, this works out great. Alice is the last person's Secret Santa.<br>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.<br>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?*<br>The tie is broken somehow, and the next cycle is traversed.Mauritsnoreply@blogger.comtag:blogger.com,1999:blog-736810000699453506.post-57822848546440100682007-01-19T06:33:42.000-08:002007-01-19T06:33:42.000-08:00Eugen's "no two-cycles" constraint i...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.Mauritsnoreply@blogger.comtag:blogger.com,1999:blog-736810000699453506.post-68137163982813949842007-01-19T07:04:28.000-08:002007-01-19T07:04:28.000-08:00Exanding audience...http://channel9.msdn.com/ShowP...Exanding audience...<br>http://channel9.msdn.com/ShowPost.aspx?PostID=273941#273941Mauritsnoreply@blogger.comtag:blogger.com,1999:blog-736810000699453506.post-84888984834076583792007-01-22T04:49:52.000-08:002007-01-22T04:49:52.000-08:00There is another difficulty with "pass the ha...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.SteveRowenoreply@blogger.com