We have a number of people who need to be divided into groups, but some people may hate other people. Divide people into a minimum number of groups, so no one is grouped with someone they do not like. (If A does not like B, then A can not be in a group with B. Each person must belong to one group.)
Incompatibilities between people are explicitly given as pairs of unordered people who can not be in a group.
Consider a possible scenario involving 10 people where the 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 made up of people (1, 4, 5) because of the incompatibility couple (4,5), which means that people 4 and 5 are incompatible and can not not belong to the same group.
For the scenario presented above, we can divide people optimally into groups that all hear, using no less than 4 groups. Here is a way to organize people into 4 groups.
GROUP #1 : ( 1, 3, 5 ) GROUP #2 : ( 2, 4 ) GROUP #3 : ( 6, 8, 10 ) GROUP #4 : ( 7, 9 )
Note that groups do not necessarily have the same number of members and that it is acceptable to have a group consisting of only one individual if necessary. But each person must be assigned to a group.
Describe an algorithm from an arbitrary incompatibility matrix among N people in the form of zero or more pairs of incompatibilities to determine a compatible group using as few groups as possible.