Algorithm to find most efficent partitioning of a set

Question

Given a set $S$ with a finite number of elements, where each $s_i\in S$ is itself a set with a finite number of elements, how do you partition $S$ using as few partitions as possible, such that all elements of $S$ in each partition are disjoint?

For example, given $$S = \{\{1,2\},\{2,3\},\{1,4\},\{1,2,4,5\},\{2,5\},\{2,3,5,6\},\{3,6\},\{4,5\},\{5,6\}\}$$

we have the following partition:

Where each row represents a separate partition. Some simplifications to the problem are that each $s_i$ contains non-negative integers less than or equal to $n$, where $n$ is the number of elements in $\cup_{r\in S} r$.

Here's a more complex partition:

Here is an example input. It took 8 partitions, which I'm pretty sure is optimal.

{{67, 68, 77, 78}, {78, 88}, {35, 36}, {71, 81}, {78, 79, 88, 89}, {79, 89}, {19, 29}, {32, 33, 42, 43}, {77, 78, 87, 88}, {65, 66, 75, 76}, {34, 35, 44, 45}, {14, 15}, {55, 65}, {22, 23, 32, 33}, {28, 29}, {70, 80}, {88, 89}, {91, 92}, {46, 47, 56, 57}, {46, 56}, {5, 6, 15, 16}, {84, 85}, {56, 57}, {44, 45}, {89, 90, 99, 100}, {68, 69}, {24, 34}, {76, 77}, {53, 54}, {6, 7, 16, 17}, {36, 37, 46, 47}, {82, 83, 92, 93}, {24, 25}, {5, 15}, {43, 53}, {9, 10, 19, 20}, {76, 77, 86, 87}, {30, 40}, {72, 73}, {3, 4, 13, 14}, {8, 9}, {78, 79}, {63, 64}, {58, 59}, {24, 25, 34, 35}, {45, 46, 55, 56}, {3, 4}, {15, 25}, {8, 9, 18, 19}, {26, 27}, {21, 22}, {11, 21}, {55, 56, 65, 66}, {14, 15, 24, 25}, {77, 78}, {98, 99}, {65, 75}, {2, 3}, {5, 6}, {51, 52}, {4, 14}, {17, 27}, {63, 73}, {7, 8, 17, 18}, {12, 22}, {65, 66}, {74, 75, 84, 85}, {56, 57, 66, 67}, {36, 37}, {94, 95}, {64, 65}, {16, 26}, {41, 42}, {90, 100}, {92, 93}, {3, 13}, {52, 53, 62, 63}, {58, 68}, {48, 58}, {45, 55}, {9, 19}, {38, 48}, {47, 57}, {34, 44}, {14, 24}, {57, 58, 67, 68}, {87, 88}, {47, 48}, {31, 32}, {29, 30}, {52, 53}, {20, 30}, {43, 44, 53, 54}, {57, 67}, {81, 91}, {26, 36}, {89, 90}, {59, 60}, {67, 68}, {93, 94}, {10, 20}, {68, 69, 78, 79}, {59, 60, 69, 70}, {4, 5, 14, 15}, {75, 85}, {23, 33}, {72, 73, 82, 83}, {42, 52}, {77, 87}, {9, 10}, {85, 86, 95, 96}, {80, 90}, {50, 60}, {62, 72}, {32, 42}, {7, 17}, {83, 84, 93, 94}, {34, 35}, {41, 51}, {79, 80}, {86, 87, 96, 97}, {49, 59}, {27, 28}, {12, 13}, {18, 19}, {29, 39}, {83, 93}, {35, 45}, {74, 75}, {67, 77}, {18, 28}, {61, 62}, {29, 30, 39, 40}, {61, 71}, {39, 49}, {53, 54, 63, 64}, {82, 83}, {37, 38}, {76, 86}, {33, 34, 43, 44}, {44, 54}, {69, 70}, {81, 82}, {2, 3, 12, 13}, {63, 64, 73, 74}, {46, 47}, {54, 55}, {39, 40}, {51, 61}, {42, 43, 52, 53}, {25, 26}, {33, 34}, {6, 7}, {60, 70}, {66, 67, 76, 77}, {27, 37}, {32, 33}, {2, 12}, {57, 58}, {73, 83}, {16, 17, 26, 27}, {1, 11}, {19, 20, 29, 30}, {27, 28, 37, 38}, {62, 63, 72, 73}, {48, 49}, {28, 38}, {19, 20}, {75, 76, 85, 86}, {88, 98}, {58, 59, 68, 69}, {64, 65, 74, 75}, {66, 76}, {15, 16}, {52, 62}, {66, 67}, {79, 80, 89, 90}, {12, 13, 22, 23}, {55, 56}, {26, 27, 36, 37}, {53, 63}, {13, 23}, {8, 18}, {83, 84}, {73, 74}, {17, 18, 27, 28}, {31, 41}, {54, 64}, {1, 2}, {7, 8}, {13, 14, 23, 24}, {16, 17}, {38, 39, 48, 49}, {97, 98}, {96, 97}, {59, 69}, {71, 72}, {88, 89, 98, 99}, {68, 78}, {99, 100}, {47, 48, 57, 58}, {18, 19, 28, 29}, {28, 29, 38, 39}, {74, 84}, {72, 82}, {22, 23}, {69, 70, 79, 80}, {44, 45, 54, 55}, {56, 66}, {40, 50}, {73, 74, 83, 84}, {86, 96}, {87, 88, 97, 98}, {25, 35}, {69, 79}, {45, 46}, {35, 36, 45, 46}, {36, 46}, {85, 95}, {23, 24}, {23, 24, 33, 34}, {25, 26, 35, 36}, {84, 85, 94, 95}, {84, 94}, {86, 87}, {33, 43}, {15, 16, 25, 26}, {64, 74}, {21, 31}, {13, 14}, {87, 97}, {17, 18}, {54, 55, 64, 65}, {22, 32}, {82, 92}, {38, 39}, {62, 63}, {37, 47}, {85, 86}, {42, 43}, {95, 96}, {39, 40, 49, 50}, {75, 76}, {4, 5}, {11, 12}, {49, 50, 59, 60}, {43, 44}, {49, 50}, {48, 49, 58, 59}, {6, 16}, {37, 38, 47, 48}, {89, 99}}

The algorithm I used to do the partitioning on the above sets works as follows: (python pseudocode)

partitions = []
for s in S:
    found_partition = False
    for p in partitions:
        if p.isdisjoint(s):
            p.update(s)
            found_partition = True
            break
    if not found_partition:
        partitions.append(set(s))

However I know this algorithm isn't optimal because I've gotten different numbers of partitions depending on the order of the input data. When the above input data is sorted, it takes 8 partitions, but otherwise it takes 11.

Answer 1

I am not sure if you are looking for an exact polynomial algorithm or not. If so, I have bad news. This problem is NP-hard, due to a reduction from the vertex cover problem. In the following, please find a brief sketch of the proof/reduction (I did not deal with decision problems, it is very straightforward reduction after you read the following).

Given an instance of the vertex cover problem $I=\langle G=(V, E) \rangle$ (and a $k$ in the instance of the decision problem), you can construct an instance of your own problem $I'= \langle S \rangle$ (and a $k$ in the instance of the decision problem) that decides the answer to the vertex cover problem. Let $G'=(V, E')$ be the complement graph of $G$, where there is an edge between two vertices $v_i$ and $v_j$ in $G'$, if and only if there is no edge between $v_i$ and $v_j$ in $G$. Assign each vertex $v_i \in V$ a set $S_i$, initially set to empty. Start with a vertex $v_1$ and for every neighbor $v_i$ of $v_1$, add the label $v_1i$ to both sets $S_1$ and $S_i$. Then, do the same thing for vertices $v_2$, ..., $v_n$. You will end up with a set $S=\{ S_1, \cdots, S_n \}$. If you solve your proposed problem over $S$, this is identical to the vertex cover of $G$.

Good news? You can apply all approximation and heuristic algorithms presented for vertex cover problem to your problem easily.