[Solved]: Is the maximum coverage variant of Vertex Cover also NP-hard?

ignougroup
Problem Detail: 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?

Asked By : John

Answered By : Yuval Filmus

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.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/32659