Input is a universe $U$ and a family of subsets of $U$, say, ${\cal F} \subseteq 2^U$. We assume that the subsets in ${\cal F}$ can cover $U$, i.e., $\bigcup_{E\in {\cal F}}E=U$.

An incremental covering sequence is a sequence of subsets in ${\cal F}$, say, ${\cal A}=\{E_1,E_2,\ldots,E_{|{\cal A}|}\}$, that satisfies

1) $\forall E\in {\cal A}, E\in {\cal F}$,

2) every newcomer has new contribution, i.e., $\forall i>1$, $\bigcup_{j=1}^{i-1}E_i \subsetneq \bigcup_{j=1}^{i}E_i$;

The problem is to find an incremental covering sequence of maximum length (i.e., with maximum $|{\cal A}|$). Note that a maximum length sequence must eventually cover $U$, i.e., $\bigcup_{E\in {\cal A}}E=U$.

I have attempted to find an algorithm or an approximate algorithm to find the longest incremental covering sequence. I was just wondering what this variant of set cover problem known as. Thank you!

  • You require your family of subsets $\cal{A}$ to cover the universe $\cal{U}$? Because then of course you can a more difficult set cover problem since you are looking for set cover with additional properties. In other words, set cover is reduces to your problem. At the wiki of set cover are also the innapproximability results for set cover. – Harry Oct 24 '14 at 11:37
  • 1
    Just an observatiion (too small to make into an answer): when your subsets are of size two then what you are looking for is essentially a spanning forest. – David Eppstein Oct 24 '14 at 17:42
  • Probably not new to the OP, but here are a few observations. (1) The optimal value is always at most |U|. Whether the optimal value is equal to |U| or not can be decided efficiently by the greedy algorithm that tries to minimize the number of covered elements. (2) The same greedy algorithm also works if all the sets in F are of size two, see David Eppstein’s comment. (3) The same greedy algorithm does not work in general (sigh). A counterexample: F={{1,2,3}, {1,4,5,6}, {2,4,5,6}, {3,4,5,6}}. – Tsuyoshi Ito Oct 25 '14 at 6:02
  • 1
    The problem does not really look like a set cover problem at all... More like a hybrid between matching and induced matching in bipartite graphs. A nice equivalent reformulation is that a family is bad if no element is covered by exactly one set in the family. The problem is to find a largest subfamily ${\cal A}$ of ${\cal F}$ such that ${\cal A}$ has no bad subfamily. – daniello Oct 28 '14 at 20:11
  • 1
    @Neal Young ${\cal F}$ is not bad because $b$ is covered by exactly one set (namely $\{a,b\}$). – daniello Nov 23 '14 at 18:15

Here I show that the problem is NP-complete.

We convert a CNF to an instance of your problem as follows. Suppose that the variables of the CNF are $n$ $x_i$'s and the clauses are $m$ $C_j$'s, where $n<m$. Let $U=\cup_i (A_i\cup B_i\cup Z_i)$ where all sets in the union are completely disjoint. In fact, $A_i=\{a_{i,j}\mid x_i\in C_j\}\cup\{a_{i,0}\}$ and $B_i=\{b_{i,j}\mid x_i\in C_j\}\cup\{b_{i,0}\}$, while $Z_i$ is any set of cardinality $k=2n+1$. Also denote $Z=\cup_i Z_i$ and fix for every $Z_i$ an increasing family of length $k$ inside it, denoted by $Z_{i,l}$ for $l=1..k$. For every variable $x_i$, we add $2k$ sets to $\mathcal F$, every set of the form $A_i \cup Z_{i,l}$ and $B_i \cup Z_{i,l}$. For every clause $C_j$, we add one set to $\mathcal F$, which contains $Z$, and for every $x_i\in C_j$ element $\{a_{i,j}\}$ and for every $\bar x_i\in C_j$ element $\{b_{i,j}\}$.

Suppose that the formula is satisfiable and fix a satisfying assignment. Then pick the $k$ sets of the form $A_i \cup Z_{i,l}$ or $B_i \cup Z_{i,l}$, depending on whether $x_i$ is true or not. These are $nk$ incremental sets. Now add the $m$ sets corresponding to the clauses. These also keep increasing the size, as the clauses are satisfiable. Finally, we can even add $k$ more sets (one for each variable) to make the sequence cover $U$.

Now suppose that $n(k+1)+m$ sets are put in an incremental sequence. Notice that at most $k+1$ sets corresponding to $x_i$ can be selected for each $x_i$. Thus, if there are no clause sets in the incremental sequence, at most $n(k+1)$ can be selected, which is too few. Notice that as soon as a clause set is selected, we can pick at most two sets corresponding to each $x_i$, a total of at most $2n$ sets. Therefore, we have to pick at least $n(k-1)$ variable sets before any clause set is picked. But as we can pick at most $k+1$ for each $x_i$, this means that for each we have picked at least $1$, as $k=2n+1$. This determines the "value" of the variable, thus we can pick only "true" clauses.

Update: Changed value of $k$ from $n$ to $2n+1$ as pointed out by Marzio.

  • 1
    A clarification: I quickly checked the construction for the unsatisfiable formula $x_1 \land \neg x_1$ ($n=k=1, m=2$) but it seems that we can build a sequence of $n(k+1)+m = 4$ of increasing sets of $\mathcal F$. Probably I make a mistake: do we have $\mathcal F= \{ \{ a_{1,0}, a_{1,1}, a_{1,2}, z_1 \}, \{ b_{1,0}, b_{1,1}, b_{1,2}, z_1\}, \{ a_{1,1}, z_1 \}, \{ b_{1,2}, z_1 \} \}$? – Marzio De Biasi Dec 4 '14 at 11:28
  • Knowing you and myself, I'm sure the mistake is mine... I think we should get ${\mathcal F}=\{\{a_{1,0},a_{1,1},z_1\}, \{b_{1,0},b_{1,2},z_1\},\{a_{1,1},z_1\}, \{b_{1,2},z_1\}\}$, but of course it's still a problem. OK, I see where I made the error, I fix it in a minute, thx! – domotorp Dec 4 '14 at 19:04
  • Ok, I'll take a look at it tomorrow! Just a note, can you write (in a comment) what is $\mathcal F$ for $x_i \land \neg x_i$ and what is the "target value" for the length of the covering sequence (is it k)? Because, in the modified answer you set $k = 2n+1$ first, then talk about $n(k+1)+m = 2n^2+2n + m$ sets are put in an incremental sequence; is it correct (I don't tried the reduction, yet) ? – Marzio De Biasi Dec 5 '14 at 0:05
  • ${\mathcal F}=\{\{a_{1,0},a_{1,1},z_1,\},\{a_{1,0},a_{1,1},z_1,z_2\},\{a_{1,0},a_{1,1},z_1,z_2,z_3\},\{b_{1,0},b_{1,2},z_1\},\{b_{1,0},b_{1,2},z_1,z_2\},\{b_{1,0},b_{1,2},z_1,z_2,z_3\},\{a_{1,1},z_1,z_2,z_3\},\{b_{1,2},z_1,z_2,z_3\}\}$ – domotorp Dec 5 '14 at 6:08
  • I think this is correct as $n(k+1)+m=6$, but we only have length $5$ incremental sequences. – domotorp Dec 5 '14 at 6:14

This is a set packing problem under the constraint that for the solution $\mathcal{A}$, for any subset $\mathcal{B} \subseteq \mathcal{A}$, we have that there is always an element in $\bigcup_{X \in \mathcal{B}} X$, which is covered exactly once.

Proof: Given a solution to your problem, it immediately has this property. Indeed, if $E_1, \ldots, E_m$ is the optimal solution to your problem, then consider a subset $\mathcal{B}$ of these sets, and assume $E_i$ is the last set in this sequence appearing in $\mathcal{B}$. By the required property that the solution is incremental, it follows that $E_i$ covers an element that no prior set covers, which implies the above property.

As for the other direction, it also easy. Start from the solution $\mathcal{A}$, find the element that is covered exactly once, set it as the last set in the sequence, remove this set, and repeat. QED.


This is a pretty natural problem....


Quick reminder: In the set packing problem, given a family of sets, find the maximal subset of sets, that comply with some additional constraint (say, no element is covered more than 10 times, etc).

  • Is this answer only proving that the question is natural, or is there something else you also claim? – domotorp Dec 5 '14 at 6:15
  • It's stating it in a simpler way. No? – Sariel Har-Peled Dec 5 '14 at 14:34
  • Yes, I agree to that. – domotorp Dec 5 '14 at 14:53

Your Answer

 
discard

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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