Create the minimum number of sets to cover all data

Question

I have a problem to create a minimum number of sets to cover the whole data set.

The problem has a data domain and a few exclusivity constraints. The exclusivity constraint states which data should not be in the same set.

The goal is to find minimum number of sets. The number of the sets doesn't have to be as balanced as possible (but would be nice to have).

Example 1:

Domain = {1, 2, 3, 4, 5, 6}
Exclusivity = 1!=2, 3!=4, 4!=5, 5!=6,

Answer is two sets: {1, 3, 5}, {2, 4, 6}

Example 2:

Domain = {1, 2, 3, 4, 5, 6}
Exclusivity = 1!=2, 2!=3, 3!=4, 4!=5

anwser is two sets: {1, 3, 5, 6}, {2, 4}

Example 3:

Domain = {1, 2, 3, 4, 5}
Exclusivity = 1!=2, 2!=3, 3!=4, 4!=5, 5!=1

answer is three sets : {1, 3}, {2, 4}, {5}

Example 4:

Domain = {1, 2, 3, 4, 5}
Exclusivity = 1!=2!=3!=4, 4!=5,

answer is four sets : {1, 5}, {2}, {3}, {4}

The != here is transitive.

Does anyone know such an algorithm to solve this problem efficiently. I couldn't remember any algorithm I leard from school that solves this problem, but that was more than 10 years ago.

Help is appreciated.

JT

Answer 1

Ignoring balance, this is graph coloring.

domain <=> vertices of the graph

set <=> all vertices with a particular color

exclusivity constraints <=> edges of the graph.

Unfortunately, graph coloring is NP-hard, and the provable approximation ratios are not good. There are many, many heuristics.

Answer 2

From my point of view I think you could create a weighted graph. For nodes that exclude each other set weight of verticies to Int.MAX, for others to 0.

Then you could try to reduce this graph for nodes that have zero routes to each-other. (I'm sure there exist some algorithm for this problem).

HTH