2
$\begingroup$

Background:

Secret Santa is a game where a group of mutual friends are randomly assigned a partner to select a gift for.

We can represent this friend group with an undirected graph $G(V,E)$, where each vertex $v \in V$ represents a friend, and each edge $e \in E$ represents a friendship.

Traditionally, $G$ is a clique: There is one edge for each pair of friends. We define the Secret Santa graph $G'(V,E')$, a directed graph where there is one incoming and one outgoing edge per node.

Example of such a traditional G and a possible associated G': G with clique size 4 on the left; G' on the right.

New problem

Now consider a non-clique $G$. This could arise in real life due to restrictions (e.g. Friends $a$ and $d$ are partners and should not buy for one another, or they do not know one another.) We want to generate a possible Secret Santa graph $G'$ as defined above, if possible.

Example of such a graph $G$ and a possible $G'$: A non-clique G with an example G'.

We can also friend graphs $G$ that have no Secret Santa graph $G'$:

A graph G that cannot have a Secret Santa graph G'

Question

Are there names for such Secret Santa graphs $G'$, when the friend graph $G$ is not necessarily a clique? If so, are there any papers with algorithms and runtimes on how to find such graphs?

$\endgroup$
  • 1
    $\begingroup$ I'm somewhat confused by your first example: I don't think your $G'$ is valid: $c$ is receiving two presents and giving one, while $b$ is giving two, and receiving one. Surely this is something that you want to avoid? At which point, your Secret Santa graphs are simply unions of directed cycle graphs, and the $G$ which produce such $G'$ are precisely those that can, by removing some edges, be made into a disjoint union of digraphs with at least two vertices, each of which has a Hamiltonian cycle. $\endgroup$ – user3482749 Nov 30 '18 at 18:25
  • $\begingroup$ My apologies, you're entirely right. I fixed the graph. But this answers my question - it looks like a "Hamiltonian cycle" is exactly what I am looking for. $\endgroup$ – gnulynnux Nov 30 '18 at 18:56
  • 1
    $\begingroup$ There is a "Secret Santa" graph if and only if the original graph has a disjoint set of cycles that covers all the vertices. I don't know whether there's a name for these graphs or not. $\endgroup$ – saulspatz Nov 30 '18 at 19:05
  • $\begingroup$ @saulspatz: Except there may be Santa loops of length 2. I guess this suggests that the definition in the question is maybe suboptimal, and we should be looking at subgraphs of directed graphs instead (whereupon your characterization is true). $\endgroup$ – Micah Nov 30 '18 at 19:37
  • $\begingroup$ @Micah Good point. I didn't think of that. $\endgroup$ – saulspatz Nov 30 '18 at 19:42
0
$\begingroup$

These notes discuss this problem in the directed graph case. Note that this solves the length-$2$ issue discussed in the comments, as well as allowing for asymmetric friendships if necessary. (For example, if Alice gave to Bob last year, you might want to disallow that from happening again while still allowing Bob to give to Alice.) If all friendships are symmetric, that just means we have edges in both directions.

The idea is as follows. Given a digraph $G$, we form a bipartite graph $E$ whose vertex set is $V(G) \times \{L, R\}$. If there is a directed edge in $G$ from $v$ to $w$, we put an edge in $E$ from $v_L$ to $w_R$. Then partitions of $G$ into vertex-disjoint cycles correspond to perfect matchings on $E$, for which there are good polynomial-time algorithms (the classic one being the Ford-Fulkerson algorithm, but there are also faster options if necessary).

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.