What is this variant of set cover problem known as?

Question

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!

Answer 1

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.

Answer 2

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