[ryansloan]

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:

A->B->C->A

D->E->F->D

Unfortunately real-life intervened and we didn't have time to decide if this was an NP complete problem or not...

[mappu]

Came to the same realisation - it's a vertex cycle cover, which can be found in polynomial time! (if one exists)

https://en.wikipedia.org/wiki/Vertex_cycle_cover

[maweki]

Well, you can always transform a true hamiltonian cycle to two cycles of a subgraph if you have a any A->B, C->D in the cycle where also A->D, B->C is in the graph. That's any 4 clique which isn't that hard, considering that the arrows can be transitive for that matter (I think, no proof attached).

Also, to show np completeness one must show reduction in both directions. I somehow doubt that any SAT-Problem is reducible to secret-santa, if secret santa isn't exactly hamiltonian cycle anyways.