<p>Seems to be in P, as it seems to be equivalent to max-wt independent set (equivalently min-wt vertex cover) in a bipartite graph, which <a href="https://stackoverflow.com/questions/24204747/maximum-weighted-independent-set-in-bipartite-graph">is in P</a>.</p>
<p>Specifically, construct the bipartite graph <span class="math-container">$G=(U, \mathcal S, E)$</span> where <span class="math-container">$$E=\{(u, S)\in U\times\mathcal S : u\in S\}.$$</span>  Make the weight of <span class="math-container">$u$</span> equal to its cost and the weight of <span class="math-container">$S$</span> equal to its profit. Then a solution (collection <span class="math-container">$C$</span> of sets) corresponds to the independent set in <span class="math-container">$G$</span> formed by the union of <span class="math-container">$C$</span> (as a set of vertices) and the elements in <span class="math-container">$U$</span> not covered by any set in <span class="math-container">$C$</span>.  Conversely any (maximal) independent set <span class="math-container">$I$</span> in <span class="math-container">$G$</span> naturally yields the corresponding solution to your problem (choose the sets in <span class="math-container">$I\cap S$</span> and the elements in <span class="math-container">$U\setminus I$</span>).</p>
<p>Note that the cost of elements covered by sets in <span class="math-container">$C$</span> is the total cost of all elements, minus the cost of elements not covered by any set in <span class="math-container">$C$</span>.  So the stated objective (profit of sets minus cost of covered elements) equals the weight of the corresponding independent set minus the total weight of all elements in <span class="math-container">$U$</span>.  So a maximum-weight independent set in <span class="math-container">$G$</span> (which can be found in polynomial time as <span class="math-container">$G$</span> is bipartite) corresponds to an optimal solution to your problem.</p>

CC BY-SA 4.0
2021-12-20T04:53:42.347Z
2021-12-20T04:53:42.347Z
Neal Young
<p>I am dealing with the following problem: Given a universe <span class="math-container">$U$</span>, let <span class="math-container">$\mathcal{S}$</span> be a family of subsets of <span class="math-container">$U$</span>. Each subset <span class="math-container">$S\in\mathcal{S}$</span> is associated with a non-negative reward, and each element <span class="math-container">$u\in U$</span> is associated with a non-negative cost. The task is to find a collection of subsets in <span class="math-container">$\mathcal{S}$</span> maximizing the difference between the total reward in the collection and the costs of elements covered by the collection.</p>
<p>I conjecture this problem is NP-hard, but so far I failed to prove so. The obvious idea from set cover (assigning -1 to each subset and -infinity to each element) fails due to the non-negativity constraint. I was also attempting to find some reduction from MAXSAT, but also with no success. Does anyone have some hints/ideas? Could this be polynomial after all?</p>

<np-hardness><set-cover>
Set cover with rewards
Mary Eiven
# Set cover with rewards

(Asked by: username_0 on 2021-12-19)

I am dealing with the following problem: Given a universe $U$, let $\mathcal{S}$ be a family of subsets of $U$. Each subset $S\in\mathcal{S}$ is associated with a non-negative reward, and each element $u\in U$ is associated with a non-negative cost. The task is to find a collection of subsets in $\mathcal{S}$ maximizing the difference between the total reward in the collection and the costs of elements covered by the collection.

I conjecture this problem is NP-hard, but so far I failed to prove so. The obvious idea from set cover (assigning -1 to each subset and -infinity to each element) fails due to the non-negativity constraint. I was also attempting to find some reduction from MAXSAT, but also with no success. Does anyone have some hints/ideas? Could this be polynomial after all?

**Tags:** np-hardness, set-cover

---

## 1 answers

### Answer by username_1 on 2021-12-20. Score: 2 | Accepted answer

Seems to be in P, as it seems to be equivalent to max-wt independent set (equivalently min-wt vertex cover) in a bipartite graph, which [is in P](https://stackoverflow.com/questions/24204747/maximum-weighted-independent-set-in-bipartite-graph).

Specifically, construct the bipartite graph $G=(U, \mathcal S, E)$ where $$E=\{(u, S)\in U\times\mathcal S : u\in S\}.$$ Make the weight of $u$ equal to its cost and the weight of $S$ equal to its profit. Then a solution (collection $C$ of sets) corresponds to the independent set in $G$ formed by the union of $C$ (as a set of vertices) and the elements in $U$ not covered by any set in $C$. Conversely any (maximal) independent set $I$ in $G$ naturally yields the corresponding solution to your problem (choose the sets in $I\cap S$ and the elements in $U\setminus I$).

Note that the cost of elements covered by sets in $C$ is the total cost of all elements, minus the cost of elements not covered by any set in $C$. So the stated objective (profit of sets minus cost of covered elements) equals the weight of the corresponding independent set minus the total weight of all elements in $U$. So a maximum-weight independent set in $G$ (which can be found in polynomial time as $G$ is bipartite) corresponds to an optimal solution to your problem.


---

