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?


1 Answer 1


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.

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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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