We have a number of people that must be partitioned into groups, but there may be people that dislike other individuals. Partition the people into the minimum number of groups such that no person is grouped with someone they don't like. (If A doesn't like B then A cannot be in a group with B. Each person must belong to exactly one group.)
The incompatibilities between people are given explicitly as unordered pairs of people that cannot be in a group together.
Consider one possible scenario involving 10 people where incompatibility pairs are given as follows:
(1,2) (1,6) (1,7) (2,3) (2,6) (2,7) (2,8) (3,4) (3,7) (3,8) (3,9) (4,5) (4,8) (4,9) (4,10) (5,9) (5,10) (6,7) (7,8) (8,9) (9,10)
In this scenario it is unacceptable to form a group consisting of persons [ 1, 4, 5 ] because of the incompatibility pair (4,5), which means that persons 4 & 5 are incompatible and cannot be in the same group.
For the scenario given above, we can divide people up optimally into groups that all get along, using no fewer than 4 groups. Here is one such way of arranging people into 4 groups.
GROUP #1 : [ 1, 3, 5 ] GROUP #2 : [ 2, 4 ] GROUP #3 : [ 6, 8, 10 ] GROUP #4 : [ 7, 9 ]
Note, that the groups do not have to have the same number of members, and it is acceptable to have a group consisting of only one individual if necessary. But each person must assigned to a group.
Describe an algorithm, given an arbitrary incompatibility matrix among N people in the form of zero or more incompatibility pairs, to determine a compatible grouping that uses the fewest groups possible.
EDIT: Here's what I have tried so far.
A greedy algorithm:
While there are persons not yet assigned to a group. Take the lowest numbered unassigned person and create a new group `g` consisting of just them. For each person `p` not yet added to a group: If they are not incompatible with anyone in the current group `g`: Add person `p` to group `g`
I have no confidence at all that this would produce the minimal number of groups though.