# Ordered set cover problem: is it NP-hard?

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.

• I would understand the newly covered elements at the time we choose $S_3$ should be $S_3\setminus(S_1\cup S_2)$ instead of $S_3\setminus(S_1\cap S_2\cap S_3)$. – John L. Aug 25 '18 at 20:55
• Can't you just reduce from SET-COVER? Given a collection of sets $S$ keep the same sets for your problem and make every weight $1$. If there is a set cover of size $k$, it corresponds to a set cover of weight $k$ in your setting. Conversely, if your problem admits a cover of weight $k$, it means you have at most $k$ sets of non-zero cost in your solution, and these correspond to a set cover. – Manuel Lafond Aug 27 '18 at 1:37

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