<p>Yes, this is closely related to the Domatic Partition problem. See the paper below.
<a href="http://epubs.siam.org/doi/abs/10.1137/S0097539700380754" rel="nofollow">http://epubs.siam.org/doi/abs/10.1137/S0097539700380754</a></p>

<p>One can get the following results. Given a set cover instance let $k$ be the minimum over all elements in $U$, the number of sets that contain that element. Then it is clear that we can have at most $k$ disjoint set covers. The paper above shows that there always exist $\max\{1, k/(c \log n)\}$ disjoint set covers where $c$ is a sufficiently large constant. This immediately gives an $O(\log n)$-approximation. Moreover, it is hard to approximate to within this factor (modulo constants). And there are examples where the number of disjoint set covers is $O(k/\log n)$. </p>

CC BY-SA 3.0
2013-05-29T11:17:38.090Z
You mean mapping the collection C to a hypergraph with vertices as universe elements, and then following the Domatic Partition problem. But as far as I understand the above paper works for graphs and not hypergraphs.
user16200
CC BY-SA 3.0
2013-05-30T17:18:18.070Z
You have look in the paper and see the randomized algorithm that gives the result for domatic paper and adapt it for disjoint set covers. It is straight forward. There could be a direct reduction as well.
Chandra Chekuri
CC BY-SA 3.0
2013-05-28T17:27:23.197Z
2013-05-28T17:27:23.197Z
Chandra Chekuri
<p>Let $U = [1..n]$ be the universe of $n$ elements and $C$ be a  collection of subsets of $U$, $C= S_1, \dots, S_m$, where $S_i \subset U$. Then the problem is to find as many partitions of $C$, such that each partition covers the universe U. The hardness results can be  derived for this problem, but are there any approximation algorithms known for this ? I gather that the geometric version of this problem has some approximation algorithms, but is there any thing known in the general case ?</p>

<ds.algorithms><approximation>
Finding maximum number of disjoint set covers
user16200
# Finding maximum number of disjoint set covers

(Asked by: username_0 on 2013-05-28)

Let $U = [1..n]$ be the universe of $n$ elements and $C$ be a collection of subsets of $U$, $C= S\_1, \dots, S\_m$, where $S\_i \subset U$. Then the problem is to find as many partitions of $C$, such that each partition covers the universe U. The hardness results can be derived for this problem, but are there any approximation algorithms known for this ? I gather that the geometric version of this problem has some approximation algorithms, but is there any thing known in the general case ?

**Tags:** ds.algorithms, approximation


---

## 1 answers

### Answer by username_1 on 2013-05-28. Score: 3

Yes, this is closely related to the Domatic Partition problem. See the paper below.
<http://epubs.siam.org/doi/abs/10.1137/S0097539700380754>

One can get the following results. Given a set cover instance let $k$ be the minimum over all elements in $U$, the number of sets that contain that element. Then it is clear that we can have at most $k$ disjoint set covers. The paper above shows that there always exist $\max\{1, k/(c \log n)\}$ disjoint set covers where $c$ is a sufficiently large constant. This immediately gives an $O(\log n)$-approximation. Moreover, it is hard to approximate to within this factor (modulo constants). And there are examples where the number of disjoint set covers is $O(k/\log n)$.

> **Comments:**
> **username_0**: You mean mapping the collection C to a hypergraph with vertices as universe elements, and then following the Domatic Partition problem. But as far as I understand the above paper works for graphs and not hypergraphs.  
> **username_1**: You have look in the paper and see the randomized algorithm that gives the result for domatic paper and adapt it for disjoint set covers. It is straight forward. There could be a direct reduction as well.  

---

