Partilhar via

Secret Santa is NP-Complete

  • Artigo

Every 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 work for us.  In 1999 a friend and I wrote a C++ app to do the work.  Though we've been running it every year, the code hasn't much changed in the intervening seven years.  It is getting dated and needs reworking. 

Toward that end, I've been contemplating the match routine lately.  The current one does something naive like:

Pick a person

Choose a match at random

If there is a conflict with that person, slide to the next one on the list.

Once a match is found, remove those people from the relative lists and pick a new person.

If a match cannot be made, start the process over.

With a small number of people and not a lot of blacklisting (husband shouldn't draw wife's name, etc.), this algorithm will work.  However, for a complicated list of people, this algorithm is nondeterministic and could theoretically run forever.  I was thus searching for a better algorithm.  One which was faster than a complete enumeration of all options and deterministic in nature.

This weekend I took the final for my Formal Models of Computation course.  (Yes, this ties in with the above--be patient) The last thing we covered was complexity classes and the concepts of P and NP.  What follows is a brief description of this concept.  For a more formal handling of the subject, check out the Wikipedia entry. 

In theoretical computer science, they don't use real computers.  Rather, they use formal models called Turing Machines.  These have the same power to solve problems that modern computers do, just a bit less efficiently.  They are a good proxy for real computers.  The speed of these machines is measured roughly in terms of the input.  So given an input of length n, a linear algorithm would take O(cn) time, where c is a constant.  We usually ignore these constants and just call it O(n) time. 

There is a class of problems called P or Polynomial-time which represent those problems that can be solved by a Turing machine in a time which is a polynomial of the input length.  That is, O(n^2), O(n^3), ... , O(n^k).  These are generally thought of as those problems that computers can efficiently solve.

There is another class of problems called NP or Nondeterministic-Polynomial-time.  These represent those problems that can be solved by a nondeterministic Turing machine in polynomial time.  A nondeterministic Turing machine is bascially one that can do more than one thing at once.  When it comes to a fork in the algorithm, it can take both forks simultaneously. 

It is assumed that NP describes a bigger universe of problems than P.  That is, P !=NP.  What takes nondeterministic Turing machines polynomial time takes regular Turing machines exponential time.  That is, they take something like O(2^n) time.

Back to my Secret Santa problem.  It was just after my final that I turned my thoughts back to solving this problem.  It then hit me that what I was trying to do was impossible.  There is a well-known NP-class problem which involves finding a Hamiltonian circuit.  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.  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, visting each node once.  In theoretical computer science this is known as a reduction.

This analysis pretty much dashes my chances of finding an elegant solution to the problem.  There is no true solution other than brute force trying each combination.  With the small number of nodes in my usual matching, this works but I still want something better.  All is not lost, however.  There are some techniques I can use to get close to the solution without necessarily trying all of the combinations which I intend to investigate.  I'll write about them after I understand more.

Wow.  I guess I did learn something practical in that class after all.

Comments

  • Anonymous
    December 19, 2006
    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. For example, if you restrict the graphs to ones where every vertex has degree 2 (circles), the Hamiltonian circuit problem is trivial. I wonder if there is a way to add reasonable constraints to the Secret Santa problem that allows for an elegant solution? Of course, the brute-force solution also has its charms... Given a set P of people P1, P2, P3... Pn; And a set E of disallowable edges E1 = P1a -> P1b, E2 = P2a -> P2b, ... Em = Pma -> Pmb; Find a Secret Santa cycle Pi1 -> Pi2 -> ... Pin -> Pi1 so that none of the edges of the set are disallowed; Algorithm: construct the set of all permutations of P that start with P1 -- this is a set of size (n-1)! Construct an enumerator to iterate through this set, starting with P1 -> P2 -> P3 ... -> Pn, and ending with P1 -> Pn -> Pn-1 -> ... P1 For each permutation, determine by inspection whether it contains any forbidden edges.  If not, use this as the solution. 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.

  • Anonymous
    December 19, 2006
    The comment has been removed

  • Anonymous
    December 21, 2006
    The comment has been removed

  • Anonymous
    December 21, 2006
    The comment has been removed

  • Anonymous
    December 21, 2006
    The comment has been removed

  • Anonymous
    December 21, 2006
    Oh, and here's a C++ implementation of the solution that works for Dirac graphs (each vertex has degree at least n/2:) http://www.geocities.com/dharwadker/hamilton/main.html (section 6 - hamilton.cpp)

  • Anonymous
    January 18, 2007
    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?

  • Anonymous
    January 18, 2007
    The comment has been removed

  • Anonymous
    January 19, 2007
    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. It is fairly trivial to write a computer program that follows this implementation.  It's certainly not NP-complete. There are several problems with this, though.

  1. Someone might draw their own name from the hat.  This is typically worked-around by having them simply draw another name.
  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.
  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: 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. 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 ... ... and so on up the chain. If you have a single Hamiltonian cycle, this works out great.  Alice is the last person's Secret Santa. 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. 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? The tie is broken somehow, and the next cycle is traversed.

  • Anonymous
    January 19, 2007
    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.

  • Anonymous
    January 19, 2007
    Exanding audience... http://channel9.msdn.com/ShowPost.aspx?PostID=273941#273941

  • Anonymous
    January 22, 2007
    The comment has been removed