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.

  • $\begingroup$ 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)$. $\endgroup$ – John L. Aug 25 '18 at 20:55
  • $\begingroup$ 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. $\endgroup$ – Manuel Lafond Aug 27 '18 at 1:37

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

| cite | improve this answer | |
  • $\begingroup$ There is minor mistake (or, you may way , typo) in the answer. It should be "your problem is NP-complete (and so, NP-hard)". Please note a problem is NP-complete implies it is NP-hard. However, a problem is NP-hard does NOT implies it is NP-complete. $\endgroup$ – John L. Sep 2 '18 at 14:33
  • $\begingroup$ The reduction only shows that the problem is NP-hard. Since it’s trivially in NP, it follows that it’s NP-complete. $\endgroup$ – Yuval Filmus Sep 2 '18 at 14:38
  • $\begingroup$ I see. Thanks for the explanation. The first statement is confusing only to people like me, then. $\endgroup$ – John L. Sep 2 '18 at 14:45

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.