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.<p>The problem you know is NP-complete has to be reduced to your Santa problem.<p>What OP described was mapping from Secret Santa to Hamiltonian circuit, not the other way around.<p>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.<p>That's why it's not that simple to prove a problem NP-complete.<p>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.<p>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.).
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.<p>See <a href="http://cstheory.stackexchange.com/questions/8563/partition-a-graph-into-node-disjoint-cycles" rel="nofollow">http://cstheory.stackexchange.com/questions/8563/partition-a...</a> for details.
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:<p>A->B->C->A<p>D->E->F->D<p>Unfortunately real-life intervened and we didn't have time to decide if this was an NP complete problem or not...
> 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.<p>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).<p>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.
Some really sloppy thinking here. He didn't really define the problem he's trying to solve in the first place.<p>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.
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.<p>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.<p>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.<p>Trying to reject permutation half way and fixing it has a tendency to cause subtle biases.
What's wrong with <i>something like</i>:<p><pre><code> 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.</code></pre>