Variation of Set Cover Problem: Finding a maximum-sized collection of disjoint set-covers

Question

I have the following problem, which seems to be similar to Set Cover.

We are given a set $U$ of elements (the universe, e.g., $U=\{1,2,3,4,5\}$). We're also given a set $S$ of subsets (e.g., $S=\{\{1\},\{2\},\{3\},\{4\},\{5\},\{1,2,5\},\{1,3,4\},\{2,3,4,5\}\}$).

The standard set cover problem asks for the minimum subset of $S$ that covers the whole universe $U$, i.e., the smallest set-cover. In our case this would be $\{\{1\},\{2,3,4,5\}\}$.

However, I'm interested in finding a collection of set-covers where each subset from $S$ is used at most once. I want to find the largest such collection possible, i.e., to find as many different, disjoint set-covers of $U$ as possible. Considering our example, the three set-covers $\{\{1\},\{2,3,4,5\}\}$ and $\{\{3\},\{4\},\{1,2,5\}\}$ and $\{\{2\},\{5\},\{1,3,4\}\}$ would be the output, since each one is a set-cover of $U$ and they are pairwise disjoint (no subset from $S$ is used in more than one set-cover).

Just testing all possible combinations of set-covers is definitely not an option. I have tried using an algorithm for set cover (ILP implementation) repeatedly, eliminating all used subsets in between runs. However, I'm certain that this strategy does not actually maximize the number of all possible covers.

Edit 1: I will try to describe the size of my problem a bit better. The typical size of $U$ is about 4000. $S$ consists of about 50 subsets. Each element of $S$ covers on average about 70% of $U$. Please keep in mind that I don't want to find all subset combinations out of $S$ that cover $U$. I just want to determine the maximum number of set covers using each subset from $S$ only once (or not at all). As of now I'm guessing the maximum number of possible covers is approximately 5.

Answer 1

The desired output from your algorithm might be exponentially large. (There could be exponentially many set covers). Therefore, you can't possibly expect to have an efficient algorithm in general.

One approach could be to code this up as a SAT (or ILP) problem, and add blocking clauses, so that in each iteration it gives you a new set cover that you haven't seen before. Whether this will be effective in practice will depend upon many factors, such as how many set covers exist.

To help us help you, I suggest you tell us more about the parameters and structure of your particular problem. What would be a typical size of $|U|$ and of $|S|$? What would be a typical number for the total number of set covers (the size of the output that you're hoping to produce)? Is there any structure in $S$ that might be helpful? The best algorithm for your particular situation is likely to depend upon these factors.

---

Edit: Thank you for the additional details! That helped. So, it sounds like your goal could be described: given $k$, test whether there exist $k$ disjoint set covers from $S$ (i.e., test whether there exists $C_1,C_2,\dots,C_k$ where $C_i \subseteq S$, $C_i$ is a set cover, and $C_i \cap C_j = \emptyset$ for all $i,j$). This is the decision problem version of your problem; if we can solve the decision problem, then we can use binary search on $k$ to find the maximum number you're looking for.

Given your problem size, the first thing I'd try would be using a SAT solver. Here's how you could formulate your problem in a way that would let you apply an off-the-shelf SAT solver. Suppose $S=\{s_1,s_2,\dots,s_{50}\}$, where each $s_i$ is a subset of the universe $U$. Introduce boolean variables $x_{i,j}$ (where $1 \le i \le 50$ and $1 \le j \le k$), with the intent that if $x_{i,j}$ is true, then the $j$-th cover $C_j$ will include $s_i$ (in other words, the $j$-th cover contains the subsets $\{s_i : x_{i,j} \text{ is true}\}$). We obtain the following constraints, which can each be expresses as CNF clauses:

• For each $i$, at most one of $x_{i,1},x_{i,2},\dots,x_{i,k}$ is true. One way to express this is as the conjunction of clauses $(\neg x_{i,j_1} \lor \neg x_{i,j_2})$ over all $j_1 \ne j_2$, i.e.,

  $$\bigwedge_{1 \le j_1 < j_2 \le k} (\neg x_{i,j_1} \lor \neg x_{i,j_2}).$$

  (Other ways of encoding this constraint are described here.) This expresses the constraint that the $k$ set-covers are disjoint.

• For each $j$, $\{s_i : x_{i,j} \text{ is true}\}$ is a set cover. In other words, for each $j$ and each $u \in U$, there exists $i$ such that $u \in s_i$ and $x_{i,j}$ is true. This can be expressed as the following conjunction of clauses:

  $$\bigwedge_{j,u} \bigvee_{i : u \in s_i} x_{i,j}.$$

• Optionally, you could break the symmetry here by imposing a lexicographic order on the set-covers. For instance, you could require that when $1 \le j_1 < j_2 \le k$, then $(x_{1,j_1},x_{2,j_1},\dots,x_{50,j_1}) < (x_{1,j_2},x_{2,j_2},\dots,x_{50,j_2})$ (using the lexicographic ordering on bit-strings of length 50).

You could then try using an off-the-shelf SAT solver and see if it is able to complete on this problem in a reasonable amount of time.