# Forming groups of people such that no group has two people that dislike each other

I had an assignment for the graph theory unit of my data structures course. The problem was given as follows:

Every person in a class has at least one other person that they dislike and will not work with. Form groups so that everyone gets along with their group members. You are not allowed to form more than $$k$$ groups in total. Given a list of pairs of people who dislike each other, and the number $$k$$, return a grouping of students if it is possible, otherwise return None.

I have found a way to generalize this problem more succinctly if it helps:

Given a binary relation $$R$$ on a set $$S$$, find an equivalence relation $$R'$$ on the set $$S$$ such that $$R \cap R'=\emptyset$$ and the size of the quotient set of $$S$$ by $$R'$$ less than $$k$$.

My attempt was to solve the problem using a DFS on the tree of partitions of $$S$$. Start with an empty partition then try to insert some person, forming a new "vertex" of the tree. Continue doing this until a leaf is reached, or a state that has already been visited is seen. The problem with this solution is that although it is correct, it is too slow. Cases with 8 groupings can take several minutes to find, and the list of visited states becomes so massive that the program runs out of memory.

def enemyDicc(dislikes):
result = {}
for x, y in dislikes:
if x in result:
else:
result[x] = {y}

if y in result:
else:
result[y] = {x}
return result

def formGroups(dislikes, max_):
enemiesOf = enemyDicc(dislikes)
ppl = list(enemiesOf.keys())
failed = []

def findFrom(people, grouping):
# dont make the same mistakes
if grouping in failed:
return None
if len(grouping) == len(ppl):
# everyone is in this grouping and we are done
return grouping
grp_ids = set(grouping.values())
# extra param for edge case at start
num_grps = max(grp_ids, default=0)
for i, person in enumerate(people):
# find a group that can take this person
found = False
for id_ in grp_ids:
hater_in_grp = any(enemy in grouping and grouping[enemy] == id_
for enemy in enemiesOf[person])
if not hater_in_grp:
grouping[person] = id_
found = True
# if no one can, try to make a new one
if num_grps < max_:
grouping[person] = num_grps + 1
found = True
# if not possible move on to next person
if found:
# try to build from this grouping
# without the person
nxt_grp = findFrom(people[:i]+people[i+1:], grouping)
# if a valid grouping is found return it
if nxt_grp:
return nxt_grp
else:
# otherwise delete the person from the grouping
del grouping[person]
# move on to the next person
# if this point is reached there is no valid grouping
failed.append(dict(grouping))
print(len(failed))
return None

return findFrom(ppl, {})

• Sounds like NP-complete to me. – John L. Jun 28 '19 at 0:23