5
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Can you enumerate all possible set covers? If so, then you can construct the corresponding graph on set covers as its vertices, and edges between those SCs with non-empty intersection. Then just find the maximum independent set. $\endgroup$ – Parham Nov 8 '13 at 11:16
  • $\begingroup$ Note that Stack Exchange is for questions and answers, not discussion. $\endgroup$ – David Richerby Nov 10 '13 at 1:00
  • $\begingroup$ having trouble following how this is different than std set cover which also has the property that subsets are used at most once. $\endgroup$ – vzn Oct 27 '14 at 18:03
  • $\begingroup$ @MahmoudA. That won't work, as the MIS doesn't have to be a cover. If we have $\{\{1\},\{3\},\{1,2,3\}\}$, then $\{1,2,3\}$ forms the only disjunct set cover, while the maximum independent set is $\{1\},\{3\}$ is not a cover. $\endgroup$ – Discrete lizard Feb 16 '17 at 20:16
1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ You can't possibly expect to have an efficient algorithm in general. We want an algorithm that works in time polynomial in the output length (or more generally, in the combined length of input and output). $\endgroup$ – Yuval Filmus Nov 8 '13 at 21:25
  • $\begingroup$ @YuvalFilmus, yup! That'd be one natural thing we could ask for (though it wasn't stated explicitly in the question). (Note that the solution proposed in my 2nd paragraph is loosely of this flavor.) But even that kind of algorithm won't help if the output length is exponential: such an algorithm will not be feasible to run to completion, if the output size is exponentially large -- I wouldn't call that "efficient". That's one reason why I asked for more clarification on the problem parameters (to help determine, e.g., whether such a condition would help or not). $\endgroup$ – D.W. Nov 8 '13 at 21:33
  • $\begingroup$ I have modified my original post in order to answer some of the commenter's questions about the size of the problem. $\endgroup$ – beac Nov 13 '13 at 8:05

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.