<p>Here I show that the problem is NP-complete.</p>

<p>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&lt;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}\}$.</p>

<p>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$.</p>

<p>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.</p>

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

CC BY-SA 3.0
2014-12-04T11:28:51.263Z
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
CC BY-SA 3.0
2014-12-04T19:04:14.610Z
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
CC BY-SA 3.0
2014-12-05T00:05:19.197Z
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
CC BY-SA 3.0
2014-12-05T06:08:44.963Z
${\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
CC BY-SA 3.0
2014-12-05T06:14:35.390Z
I think this is correct as $n(k+1)+m=6$, but we only have length $5$ incremental sequences.
domotorp
CC BY-SA 3.0
2014-12-05T08:42:15.577Z
Ok, now I understand it; nice reduction!
Marzio De Biasi
CC BY-SA 3.0
2014-12-03T22:51:20.150Z
2014-12-05T06:12:32.617Z
2014-12-05T06:12:32.617Z
domotorp
<p>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. </p>

<p>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.</p>

<p>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.</p>

<hr>

<p>This is a pretty natural problem.... </p>

<hr>

<p>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).</p>

CC BY-SA 3.0
2014-12-05T06:15:55.800Z
Is this answer only proving that the question is natural, or is there something else you also claim?
domotorp
CC BY-SA 3.0
2014-12-05T14:34:08.353Z
It's stating it in a simpler way.  No?
Sariel Har-Peled
CC BY-SA 3.0
2014-12-05T14:53:39.310Z
Yes, I agree to that.
domotorp
CC BY-SA 3.0
2014-12-05T02:40:52.977Z
2014-12-05T02:46:52.903Z
2014-12-05T02:46:52.903Z
Sariel Har-Peled
<p>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$.</p>

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

<p>1) $\forall E\in {\cal A}, E\in {\cal F}$,</p>

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

<p>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$.</p>

<p>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!</p>

CC BY-SA 3.0
2014-10-24T11:37:52.673Z
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
CC BY-SA 3.0
2014-10-24T17:42:53.853Z
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
CC BY-SA 3.0
2014-10-25T06:02:33.743Z
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
CC BY-SA 3.0
2014-10-28T20:11:28.487Z
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
CC BY-SA 3.0
2014-11-05T03:10:14.643Z
Thank you, @daniello. But I didn't know how to view it as a hybrid between matching and induced matching in bipartite graphs. Would you give me some hints? Thank you!
Alex
CC BY-SA 3.0
2014-11-23T17:22:50.513Z
@daniello, re: _``A largest subfamily $\cal A$ such that $\cal A$ has no bad subfamily.''_  If $\cal F = \{\{a,b\}, \{a\}\}$, then the incremental covering sequence $\{a\}$, $\{a,b\}$ has length 2, but $\cal F$ is bad because $a$ is not covered by exactly one set in $\cal F$.  So your characterization would give the answer 1, wouldn't it?  What am I missing?
Neal Young
CC BY-SA 3.0
2014-11-23T18:15:41.707Z
@Neal Young ${\cal F}$ is not bad because $b$ is covered by exactly one set (namely $\{a,b\}$).
daniello
CC BY-SA 3.0
2014-12-03T22:13:21.030Z
This reminds me to finding the height of a poset/longest path in an acyclic digraph. The only difference is that the poset is given by some generators. (Notice that we can suppose that F is closed under union.)
domotorp
<cc.complexity-theory><ds.algorithms><approximation-algorithms><optimization><set-cover>
What is this variant of set cover problem known as?
Alex
# What is this variant of set cover problem known as?

(Asked by: username_0 on 2014-10-23)

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!

**Tags:** cc.complexity-theory, ds.algorithms, approximation-algorithms, optimization, set-cover

> **Comments:**
> **username_1**: 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.  
> **username_2**: 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.  
> **username_3**: 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 username_2’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}}.  
> **username_4**: 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.  
> **username_0**: Thank you, @username_4. But I didn't know how to view it as a hybrid between matching and induced matching in bipartite graphs. Would you give me some hints? Thank you!  
> **username_5**: @username_4, re: _``A largest subfamily $\cal A$ such that $\cal A$ has no bad subfamily.''_  If $\cal F = \{\{a,b\}, \{a\}\}$, then the incremental covering sequence $\{a\}$, $\{a,b\}$ has length 2, but $\cal F$ is bad because $a$ is not covered by exactly one set in $\cal F$.  So your characterization would give the answer 1, wouldn't it?  What am I missing?  
> **username_4**: @username_5 ${\cal F}$ is not bad because $b$ is covered by exactly one set (namely $\{a,b\}$).  
> **username_6**: This reminds me to finding the height of a poset/longest path in an acyclic digraph. The only difference is that the poset is given by some generators. (Notice that we can suppose that F is closed under union.)  

---

## 2 answers

### Answer by username_6 on 2014-12-03. Score: 7

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

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.

> **Comments:**
> **username_7**: 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 \}  \}$?  
> **username_6**: 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!  
> **username_7**: 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) ?  
> **username_6**: ${\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\}\}$  
> **username_6**: I think this is correct as $n(k+1)+m=6$, but we only have length $5$ incremental sequences.  
> **username_7**: Ok, now I understand it; nice reduction!  

---

### Answer by username_8 on 2014-12-05. Score: 0

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).

> **Comments:**
> **username_6**: Is this answer only proving that the question is natural, or is there something else you also claim?  
> **username_8**: It's stating it in a simpler way.  No?  
> **username_6**: Yes, I agree to that.  

---

