Maximum set cover with non-overlap

Question

Let the universe be the set $U$ and a set of subsets $S$ be such that $\cup_{s \in S} s = U$. I am interested in computing the longest sequence of sets $s_1, ..., s_k$ such that:

1. $s_i \in S$ $\forall i \in [k]$

2. $s_i \not\subseteq \cup_{j=1}^{i-1} s_j$ (so each $s_i$ adds at least one new element on top of the existing $i-1$ sets)

Is there a polynomial time algorithm that can compute this longest sequence of sets given a $(U, S)$ instance? Or is this known to be hard (a reference paper on this would be much appreciated)?

Answer 1

Consider the decision version of the set-cover problem: given a collection of sets $S_i \subset U$, we need to determine whether there exists a cover of size at least $k$.

Given such an instance, we create $k$ dummy elements $e_{d_1}, \dots, e_{d_k}$. Now, for each of the subsets $S_i$, we create $k$ copies for each such $e_{d_j}$.

This serves as a reduction to the set-cover variant given in the question. More specifically, if we can get a sequence of length $k$ (at least), then we do indeed have an original set-cover of size $k$. The formal proof is left for the reader.

Hence, the considered problem is NP-hard.