0
$\begingroup$

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:

enter image description here

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:

enter image description here

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.

$\endgroup$
  • $\begingroup$ "using as few partitions" ​ -> ​ "into as few parts" ​ ​ ​ ? ​ ​ ​ ​ ​ ​ ​ ​ $\endgroup$ – user12859 Jan 23 '18 at 3:23
  • $\begingroup$ Into as few subsets (such that each subset has elements such that any pair of elements from the same subset is disjoint) $\endgroup$ – J. Antonio Perez Jan 23 '18 at 3:30
1
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.