Graph theory - Secret Santa problem | Tech Off

Matthew van Eerde
AKA Maurits

There's a blog post on Steve Rowe's blog that I've been following, applying graph theory to the Secret Santa tradition:

Secret Santa is NP-complete

Eugen Buehler proposed a constraint that got me thinking. I couldn't come up with an answer immediately, and the post is interesting as a whole, so I thought I'd extend the audience to C9/Techoff.

The general problem (in English and Mathematician-ese:)

Given a bunch of people
(Given a set of vertices V)

... and a set of rules as to who-can-give-to-whom...
(And a set of allowable edges E... thus creating a graph (G, V, E))

... is there a fast algorithm to print out a list of who should give to whom...
(Find a subgraph S in polynomial time)

... so that...
(where)

THE HAMILTONIAN PROBLEM
a) ... the chain forms a single circle?
(S is a single cycle of degree |V|)

THE PASS-THE-HAT PROBLEM
b) ... everyone gives to someone else?
(every vertex in V has degree 2 in S)

EUGEN'S PROBLEM
c) ... everyone gives to someone else, and no-one gives to the person who gave to them?
(every vertex in V has degree 2 in S, and there are no two-cycles in S)

THE ANSWERS

a) seems to be "no", unless you can add additional constraints... for example, if every vertex has degree at least |V|/2, then you're fine. If you do find a polynomial algorithm for this, you're on the short list for a Fields medal!

b) seems to be "yes", by the pass-the-hat algorithm

c) is the interesting bit. Any takers?

JohnAskew
9 girl in pink sweater

Aren't a) and c) the same?

Matthew van Eerde
AKA Maurits

Fair question...

Suppose the people are Alice, Bob, Charlize, Daniel, Eglantine, and Frank

The rules are, Alice and Eglantine can't give to each other (they're sisters, let us suppose)

Alice => Bob => Charlize => Daniel => Eglantine => Frank (=> Alice)
is a solution to a), b), and c)
In fact, any solution to a) is a solution to b) and c)

Alice => Bob => Charlize (=> Alice)
Daniel => Eglantine => Frank (=> Daniel)
is a solution to b) and c)
In fact, any solution to c) is a solution to b)
But it's not a solution to a) because there are two cycles rather than one.

Alice => Bob (=> Alice)
Charlize => Daniel => Eglantine => Frank (=> Charlize)
is a solution only to b).
It's not a solution to a) because there are two cycles instead of one;
It's not a solution to c) because Alice and Bob are each other's Secret Santa (Alice => Bob (=> Alice) is a 2-cycle)