<p>Take $S_i$ to be the edges of a graph $G$. Then, a partition $F$ of size $k$ corresponds to an edge-coloring of $G$; the minimum such $k$ corresponds to the chromatic index of $G$. Edge-coloring is known to be NP-complete: <a href="http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.97.5480&amp;rep=rep1&amp;type=pdf&amp;rct=j" rel="nofollow">"The NP-Completeness of Edge-Colouring"</a>.</p>

CC BY-SA 3.0
2011-12-07T21:19:14.883Z
2011-12-07T21:19:14.883Z
mhum
<p>Given a family of sets $F = S_1, ..., S_n$ of elements from a universe $U$, find the minimal integer $k$ for which there is a partition of $F$ of size $k$, such that every two sets in the same partition are disjoint. Formally, we want $P_1, ..., P_k$ such that for every $1 \leq i,j \leq k$, we have $P_i \subseteq F$ and $P_i \cap P_j = \emptyset$. Furthermore, for every $S,T \in P_i$ we have $S \cap T = \emptyset$. Finally, $\bigcup P_i = F$.</p>

<p>We can ask the same question as a decision problem: $\lbrace U,F,k \rbrace \in MIN-SET-PARTITION$ iff there is a partition (as described above) of $F$ of size $k$.</p>

<p>My intuition is that this is indeed NP-hard and that someone has probably already thought about it. I'd be happy to get a reference or a description of a reduction.</p>

<p>Thanks!</p>

<cc.complexity-theory><np-hardness>
Is the problem "MIN-SET-PARTITION" an NP-hard problem?
Guy
# Is the problem "MIN-SET-PARTITION" an NP-hard problem?

(Asked by: username_0 on 2011-12-07)

Given a family of sets $F = S\_1, ..., S\_n$ of elements from a universe $U$, find the minimal integer $k$ for which there is a partition of $F$ of size $k$, such that every two sets in the same partition are disjoint. Formally, we want $P\_1, ..., P\_k$ such that for every $1 \leq i,j \leq k$, we have $P\_i \subseteq F$ and $P\_i \cap P\_j = \emptyset$. Furthermore, for every $S,T \in P\_i$ we have $S \cap T = \emptyset$. Finally, $\bigcup P\_i = F$.

We can ask the same question as a decision problem: $\lbrace U,F,k \rbrace \in MIN-SET-PARTITION$ iff there is a partition (as described above) of $F$ of size $k$.

My intuition is that this is indeed NP-hard and that someone has probably already thought about it. I'd be happy to get a reference or a description of a reduction.

Thanks!

**Tags:** cc.complexity-theory, np-hardness


---

## 1 answers

### Answer by username_1 on 2011-12-07. Score: 4 | Accepted answer

Take $S\_i$ to be the edges of a graph $G$. Then, a partition $F$ of size $k$ corresponds to an edge-coloring of $G$; the minimum such $k$ corresponds to the chromatic index of $G$. Edge-coloring is known to be NP-complete: ["The NP-Completeness of Edge-Colouring"](http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.97.5480&rep=rep1&type=pdf&rct=j).


---

