Cook completeness of a variant of Vertex Cover

Question

Is this variant of Vertex Cover Cook-complete for $\mathrm{NP}$?

Input: An undirected graph $G(V, E)$ together with a vertex cover $C\subseteq V$

Output: YES if there exists a vertex cover $C'\subseteq V$ such that $|C'|=|C|-1$, NO otherwise

Answer 1

First it is obvious that the above problem is in NP. I think there is even a Karp reduction from the well-known clique problem. It uses the well-known reductions from clique problem to independent set problem and from independent set problem to vertex cover problem.

The clique problem is as follows:

Given: a graph $G$ of size $n$, parameter $k$

Output: Yes iff there is a clique in $G$ of size $k$.

Now, first we add a clique of size $k-1$ in $G$. For sake of presentation, we denot the resulted graph by $G'$. Then, we create the corresponding complement of $G'$, denoted by $\hat{G}$. Denote $\hat{G}=(\hat{V},\hat{E})$ and let $V_{clique} \subseteq \hat{V}$ be the set of vertices corresponding to the original clique of size $k-1$ in $G$. The reduction is a polynomial transformation. Note that $|\hat{V}|=n+k-1$

The graph $G$ contains a clique of size $k$ if and only if $G'$ contains a clique of size $k$, since adding a clique of size $k-1$ does not effects if $G$ has a clique of a larger size. Using the same arguments done in reduction from clique problem to the independent set problem and from independent set problem to vertex cover problem, we derive that $G$ contains a clique of size $k$ if and only $\hat{G}$ contains a vertex cover of size $|\hat{V}|-k=n-1$.

Using similar arguments, we derive that $V_{clique}$ is an independent set in $\hat{G}$, and thus the set $\hat{V}\setminus V_{clique}$ is a vertex cover in $\hat{G}$ of size $|\hat{V}|-(k-1)=n$.

Finally, let $L_{clique}$ and $L_{vertex}$ be the corresponding languages of the clique and the described vertex cover problems. Then, $(G,k) \in L_{clique}$ iff $(\hat{G},\hat{V}\setminus V_{clique}) \in L_{vertex}$ (i.e., there exists a clique of size $k$ in $G$ iff there is a vertex cover of size $|\hat{V}\setminus V_{clique}|=n-1$ in $\hat{G}$).