Is the maximum coverage variant of Vertex Cover also 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 &gt; 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 &gt; (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.