2
$\begingroup$

This is a homework question. I need to prove that the following language is in NP Complete:

3-VERTEX-COVER = $\{\langle G,k\rangle \mid$ G is an undirected graph, each vertex in $G$ has at most $3$ incident edges, and there is a vertex cover of size $k$ in $G\}$

Showing that it is in NP is easy. Now, to show that it is in NPC I thought about showing a reduction from Vertex-Cover. But I can't seem to think of what to do with a graph I get as <G,k> which is in Vertex-Cover, to make each vertex degree at most 3 without changing the vertex-cover property. Any hints?

$\endgroup$
  • $\begingroup$ You can change the vertex cover property as long as it's in a controlled way. $\endgroup$ – Yuval Filmus Jun 2 '15 at 13:21
1
$\begingroup$

Hint: Here is how to handle vertices of degree 4 (taken from Alimonti and Kann).

Let $v$ be a vertex of degree $4$, with neighbors $x_1,x_2,x_3,x_4$. Replace $v$ with a path $v_1-w-v_2$ and connect $x_1,x_2$ to $v_1$ and $x_3,x_4$ to $v_2$ (arbitrarily). A vertex cover in the original graph containing $v$ corresponds to a vertex cover in the new graph containing $v_1,v_2$. A vertex cover in the original graph not containing $v$ corresponds to a vertex cover in the new graph containing $w$. In total, we get that the original graph has a vertex cover of size $k$ iff the new graph has a vertex cover of size $k+1$.

The same idea works for vertices of higher degree.

$\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.