2
$\begingroup$

In Chapter 3 of "Approximation Algorithms for NP Hard Problems" edited by Prof. Dorit S. Hochbaum, there is such a sentence that "Maximum Coverage Problem is clearly NP-hard, as Set Cover is reducible to it" in p.135.

Given a set system G and a parameter k, Maximum Coverage Problem is to find k sets such that the elements covered is maximized, and Set Cover Problem is to identify the smallest size of sets so that all elements are covered.

I am curious about how this reduction is conducted?

Further, considering the Vertex Cover problem which is to find a cover with smallest number of vertices, can I reduce this problem to the following problem in the same way:

The problem of concern:

Given a Graph and a parameter k, find k vertices such that the number of edges linked to these vertices is maximized.

Is this problem also NP hard?

$\endgroup$

1 Answer 1

4
$\begingroup$

Optimization problems cannot be NP-complete. Only decision problems – where the answer is YES or NO – can be NP-complete. This is because the notion of NP-completeness is defined only for decision problems. When we (loosely) say that an optimization problem is NP-complete, we really mean that their decision version is NP-complete.

The decision version of Set cover: given a set system $S$ with union $U$ and a number $r$, can we cover $U$ with $r$ sets from $S$?

The decision version of Maximum coverage is: given a set system $S$, a number $r$ and a number $t$, are there $r$ sets from $S$ that together cover at least $t$ elements?

See if you can prove that the decision version of Maximum coverage is NP-complete given that the decision version of Set cover is NP-complete, and then see if you can do the same for your new problem related to Vertex cover.


I should mention that Uri Feige proved in 1998 the following strong result regarding Maximum coverage. There is a polytime reduction $f$ taking a 3CNF $\varphi$ to an instance $(S,r,t)$ of Maximum coverage such that:

  1. If $\varphi$ is satisfiable then there are $r$ sets from $S$ that together cover at least $t$ elements.

  2. If $\varphi$ is not satisfiable then all choices of $r$ sets from $S$ cover at most $(1-1/e)t$ elements.

Informally, we say that it is NP-hard to approximate Maximum coverage up to $1-1/e$. Why?

A polytime algorithm $A$ for Maximum coverage is a $\theta$ approximation if given an instance $(S,r)$ with optimal value $O$, $A$ outputs a subset of $S$ of size $r$ that covers at least $\theta O$ elements. If there was a polytime $1-1/e+\epsilon$ approximation algorithm for Maximum coverage, for any $\epsilon > 0$, then you could use it to solve 3SAT, as follows:

  1. Given $\varphi$, run $f$ and calculate the instance $(S,r,t)$.

  2. Run $A$ on $(S,r)$, getting a cover which covers $B$ elements.

  3. $\varphi$ is satisfiable iff $B > (1-1/e)t$.

I leave you to figure out why this works.

The approximation ratio $1-1/e$ is achieved by the greedy algorithm, so this result is optimal.

$\endgroup$
4
  • $\begingroup$ Can I understand the reduction from the decision version of Set Cover (SC) to the decision version of Maximum Coverage (MC) as follows: when t=|U|, the MC is the same as SC, thus SC is a speical case of MC? $\endgroup$
    – John
    Nov 5, 2014 at 5:49
  • $\begingroup$ Set cover is not a special case of maximum coverage since the optimization criterion is different. But asking whether the entire universe can be covered using $t$ sets can be formulated using both set cover and maximum coverage. $\endgroup$ Nov 5, 2014 at 14:38
  • $\begingroup$ for any instance of decision version of Set Cover, I can find an instance of decision version of Maximum Coverage by setting t=|U|, and their answers are the same. Thus, the decision version of Set Cover is reducible to the decision version of Maximum Coverage. Is that right? $\endgroup$
    – John
    Nov 8, 2014 at 3:28
  • $\begingroup$ Yes, this is correct. $\endgroup$ Nov 8, 2014 at 5:12

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.