How to partition disagreeable people into compatible groups

Question

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.

Answer 1

You are essentially asking this: "Given a graph $G=(V,E)$ where each vertex in $V$ denotes a person and each edge $(u,v) \in E$ means that $u$ is incompatible with $v$, what is the minimum number of colors required to color the vertices of $V$ such that no edge in $E$ has both endpoints of the same color?"

In other words, given any graph $G$ (which can always be realized with a suitable set of incompatibilities), find the chromatic number $\chi(G)$ of $G$.

This is a well-known NP-hard problem. In particular, it is already NP-hard to decide whether $\chi(G) \le 3$. For the special case of $2$ colors, $\chi(G) \le 2$ can be decided in linear time (just check whether $G$ is bipartite, which also gives you the corresponding coloring if that is the case).

However, since you are just asking for an algorithm (no mention of a polynomial-time complexity or even efficiency) you might as well enumerate all existing colorings in $O(3^{|V|} + \dots + \chi(G)^{|V|}) = O(\chi(G)^{|V|})$ time. This can be improved to $O(2.2461^{|V|} )$ time, see: https://epubs.siam.org/doi/10.1137/070683933

Finally, there is simple linear-time greedy algorithm that uses at most $\Delta(G)+1$ colors, where $\Delta(G)$ is the maximum degree of $G$: Examine the vertices of $G$ one at a time, color a vertex with any color that is not already used by any of its neighbors.

This is the relevant Wikipedia page: https://en.wikipedia.org/wiki/Graph_coloring .

EDIT

Your algorithm is iteratively computing maximal independent sets of $G$. Similarly to the greedy algorithm, it will return a coloring with at most $\Delta(G)+1$ colors. To see this, suppose that there is a vertex $v$ of color (group) $\Delta(G)+2$. Then, since $v$ has not been added to any of the first $\Delta(G)+1$ groups, it must have at least one neighbor in each of those groups. This means that the degree of $v$ is at least $\Delta(G)+1$, a contradiction.

Here is a tight example for both algorithms (vertices are examined in increasing order of their label):

Answer 2

If writing an algorithm that finds an optimal solution is too hard, or runs too slow, you can somewhat improve your algorithm.

1. Go through all pairs (a, b). If a dislikes b but b likes a then change that to "b dislikes a". It doesn't change the solution, but it makes it easier to talk about things.

2. Find pairs that always fit together. Go through all pairs (a, b). If a likes b, and also likes everyone whom b likes, then remove a from the problem altogether, solve the problem, and add a to b's group. This may reduce the numbers a bit.

3. Whenever you have two or more people in a group, immediately add everyone who likes everyone in the group and who likes everybody whom everybody in the group likes. Adding any such person doesn't increase the total dislike of the group. 1 to 3 are things that you should always do because they are optimal.

4. When you consider the next person to add to the group, find someone who dislikes the minimum number of people not already disliked by the group (increase the total dislike of the group by the smallest possible amount), and of those pick the one who dislikes most people. (Someone who dislikes many people is bad news. So if we can stick that person into a group that already dislikes most of the people that person dislikes, we minimise the damage that person can handle).

5. Run your algorithm repeatedly, taking random decisions instead of just arbitrary ones. Then pick the best output of those runs.