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.
Is 'double max-$k$ vertex-cover' NP-hard?
algorithms;graphs;np hard;set cover
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.