Consider the following problem, which I have called '$\mathsf{\text{double max $k$-vertex-cover}}$':

Given an undirected graph $G=(V,E)$ and integers $k$ and $t$, does there exist a set of vertices $V'\subseteq V$ of size at most $k$ such that the set $\{(u,v)\in E\mid u\in V' \wedge v \in V' \}$ has a size of at least $t$?

Is this problem NP-hard?

I suspect it is, since the similar problem of max $k$-vertex cover is NP-hard. The same trick for that problem, setting $t=|E|$, does not apply here, as that gives the trivial answer of $|V|-\#\text{zero-degree vertices}$ (in other words, double max vertex-cover is a trivial problem).

Unfortunately, I have been unable to find a reduction. This question seems related, but does not solve this problem for the same reason a reduction from minimum vertex cover fails. (A generalisation of this problem to set covering would look similar to that question)

Background: I encountered this problem in an attempt to show NP-hardness of another problem in this answer, but I think this problem is interesting on its own.


It was easier for me to show that the $k$-clique problem is a special case of this problem.

On an input graph $G$ and an integer $k$, the this special case is defined by $G$,$k$,$t$, with $t=\binom{k}{2}=k(k-1)/2$. Observe that some $V'\subseteq V$ of size $k$ is a clique in $G$ if and only if the set $V'$ covers at least $\binom{k}{2}$ edges twice.

Since the NP-hard problem $k$-clique is a special case of 'double max-$k$ vertex-cover', the problem 'double max-$k$ vertex-cover' is NP-hard.

| cite | improve this answer | |

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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