I'm looking for a pen and paper algorithm that will output (if possible) a way to sit around a table that is acceptable to all participants, while preserving as much privacy as possible in who finds whom an acceptable neighbor.
More precisely, the input of the algorithm is a positive integer $n$ for the number of people, and a set $A$ of pairs $(a, b) \in Z_n \times Z_n$ (such pair means that $a$ is willing to sit next to $b$.
The pen and paper algorithm must return (if it exists) a cyclic permutation $\sigma$ of $Z_n$ such that:
- $\sigma(x) \neq x \quad \forall x$
- $\sigma(a) = b$ implies $(a, b) \in A$ and $(b, a) \in A$
If it doesn't exist the algorithm should say so.
Each participant $x$ decides which tuples $(x, y)$ appear in $A$, and the algorithm should minimize the information that other people can infer, expecially the information about missing couples.
The best I've come up with is one person collecting all the tuples, written on individual pieces of paper, and trying to form such a cycle while uncovering a minimal amount of pieces of paper. This is very far from optimal, is there something better?
One solution, which I think maintains privacy pretty well, but may take a while if A is sparse, would be to just pick random permutations and have a secret ballot vote to see if anyone disapproves of the permutation (where the person opening the votes stops after a single NO vote, so as to make it harder to know the number of people who disapprove).