0
$\begingroup$

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

$\endgroup$
1
  • 1
    $\begingroup$ In other word, is it still very hard to incrementally improving a given solution to an $\mathrm{NP}$-complete? Seems that knowledge of a solution does not help obtain a slightly better one. $\endgroup$ Aug 27 '18 at 8:02
0
$\begingroup$

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}$).

$\endgroup$

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.