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?
Is the maximum coverage variant of Vertex Cover also NP-hard?
complexity theory;graphs;reductions;np hard
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:If $\varphi$ is satisfiable then there are $r$ sets from $S$ that together cover at least $t$ elements.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:Given $\varphi$, run $f$ and calculate the instance $(S,r,t)$.Run $A$ on $(S,r)$, getting a cover which covers $B$ elements.$\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.