How to solve the Secret Santa Problem using graph theory

Abstraction: Secret Santa assignment as Hamiltonian cycle solved with backtracking DFS

Key points:

• The Secret Santa problem with constraints (certain pairs cannot exchange gifts) is equivalent to finding a Hamiltonian cycle in a graph where nodes are participants and edges represent allowed pairings
• The Hamiltonian cycle problem is NP — no polynomial-time algorithm exists; it is related to the Traveling Salesman Problem, but Secret Santa only needs any valid cycle, not the optimal one
• A naive O(n) algorithm works well without constraints; adding constraints can cause dead-ends requiring restart or backtracking
• Depth-first search with backtracking finds the first valid Hamiltonian cycle; for few constraints it typically solves in ~N steps for N participants
• With 100 participants and 50 constraints each, brute-force backtracking may require up to ~1.5M steps in the worst case
• Engineering mitigation: limit participants to 3 constraints each to keep the search tractable

Connections: Graph Theory · Backtracking Search · Np Problems

Source: https://medium.com/pragmatic-computer-science/how-to-solve-the-secret-santa-problem-using-graph-theory-a6b216ccc622