Christmas is less than a month away. With your friends Bob and Charlie you decide that this year it would be nice to have a Secret Santa (http://en.wikipedia.org/wiki/Secret_Santa).
However, you immediately realize that there is no way for three people to exchange gifts anonymously! If you buy a gift for Bob, you also know that Bob will buy a gift for Charlie, and that Charlie will buy your gift.
With four friends (and a complete graph whose edges represent possible exchanges) a solution seems possible. But if you start removing edges you could obtain a graph for which no solution guarantees anonymity…
How do you formally define anonymity in a graph? and how do you check if a graph has this property? what is the complexity of this problem? This paper, recently and timely accepted for publication in Elsevier Computers and Operations Research, investigates the problem:
- A. Bettinelli, L. Liberti, F. Raimondi, D. Savourey, The Anonymous Subgraph Problem, to appear in Computers & Operations Research, Elsevier (PDF preprint here).
The paper shows that, in addition to Secret Santa, this problem has practical applications in networking and routing, and in the study of vehicular networks.