2
$\begingroup$

You are given an irreflexive symmetric (but not necessarily transitive) "enemies" relation on a set of people. In other words, if person A is an enemy of a person B, then B is also an enemy of A. How can you divide up the people into two houses in such a way that every person has at least as many enemies in the other house as in their own house?

$\endgroup$
1
  • $\begingroup$ I think I don't understand the question clearly. Could you elaborate on the following? "How can you divide up the people into two houses in such a way that every person has at least as many enemies in the other house as in their own house?" $\endgroup$
    – Henry
    Nov 9 '13 at 7:25
1
$\begingroup$

Divide the people up however you like. Then, if there is anyone with more enemies in their own house than the other house, make them switch houses. (If there are multiple candidates, pick any one you like.) Keep doing this until everyone has at least as many enemies in the other house as in their own. Because each switch (by construction) reduces the total number of pairs of enemies that share a house, the procedure must terminate.

This is known as the "Happynet" problem. While it is simple to find a solution, as just described, no polynomial-time algorithm for finding one is known. (The algorithm I described can take exponential time in the worst case.)

$\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.