Ordered set cover problem: is it NP-hard?

Question

Given a set of elements $U=\{1,2,\ldots,n\}$ and a collection of $m$ sets $\{S_1,S_2,\ldots,S_m\}$ whose union equals $U$. Each element $e$ of a set $S_i$ has a weight $w_i(e)$. The weight $w(S_i)$ of the set $S_i$ is defined as $w(S_i):=\max_{e\in S_i}w_i(e)$.

The problem is to choose an ordered collection of sets $O$ from $\{S_1,S_2,\ldots,S_m\}$ whose union is $U$ and its total weight is minimum. Here, if $O=\{S_1,S_2,\ldots,S_p\}$, then we choose $S_1$, then we choose $S_2$, etc. We define the total weight $W(O)$ as the sum of the weight of the sets covering new elements, i.e. $$W(O)=w(S_1)+w(S_2\backslash S_1)+\ldots+w(S_p\backslash\bigcup_{i=1}^{p-1} S_i),$$ since we choose $S_1$ first, then all elements of $S_1$ are new. At the time we choose, $S_2$, the newly covered elements are $S_2\backslash S_1$, etc.

Answer 1

The decision version of your problem is NP-hard (and so, NP-complete), by reduction from SAT.

Let $\varphi$ be a SAT formula on variables $x_1,\ldots,x_n$ and clauses $C_1,\ldots,C_m$. The universe will be $\{x_1,\ldots,x_n,C_1,\ldots,C_m\}$. For every literal $x_i$ or $\bar{x}_i$, there will be a set $S_i$ or $\bar{S}_i$ consisting of $x_i$ together with all clauses satisfied by the literal, in which all elements have unit weight. This instance has a solution of weight at most $n$ if and only if $\varphi$ is satisfiable.

Indeed, if $\varphi$ is satisfiable, then the sets corresponding to a satisfying assignment are a solution of weight $n$, in any order.

Going in the other direction, Suppose that $T_1,\ldots,T_r$ is a solution of weight at most $n$. Any solution must cover $x_1,\ldots,x_n$, so it must contain either $S_i$ or $\bar{S}_i$. If a solution contains both $S_i$ and $\bar{S}_i$, then the one which appears later must have zero cost, that is, its elements must all be covered by preceding sets; so the solution remains a solution even if we remove it. Therefore we can assume that exactly one of $S_i,\bar{S}_i$ appears. The corresponding truth assignment is easily seen to be a satisfying assignment of $\varphi$.