I'm trying to prove the Connected Vertex Cover problem is NP-complete. That is given a graph $G=(V,E)$ and integer $k$, is there a subset $X$ of $V$ such that $|X|≤k$ and that for every edge $(u,v)\in E$ at least one of $u$ and $v$ are in $X$. Furthermore, the subgraph $G[X]$ induced by $X$ must be connected.

I know the structure of an NP-complete proof. But I have no idea what problem to reduce to connected vertex cover and how to go about it.

  • $\begingroup$ Have you tried to reduce from (ordinary) vertex cover? $\endgroup$ – D.W. May 28 '18 at 21:50
  • $\begingroup$ I don't see how I alter the input so that I can use Connected Vertex Cover. Clearly if G has a connected vertex cover, then it has a normal vertex cover. But if G has a vertex cover, there's no guarantee the subgraph induced by the vertex cover is connected. $\endgroup$ – CrossGuard May 28 '18 at 22:36
  • $\begingroup$ Please don't delete your question after you've already gotten an answer. That is impolite to answerers, who are writing not only for your benefit but also for the benefit of anyone else who has the same question in the future. Thank you. $\endgroup$ – D.W. May 29 '18 at 20:06

(First, a side note: it happens that Connected Vertex Cover isn't actually NP-hard for all classes of graphs. In particular, it's solvable in polynomial time in chordal graphs and graphs with maximum degree 3. However, it is NP-hard for planar graphs with maximum degree 4 in particular, and that's the easiest case to prove.)

For this, you'll want to reduce from Planar Vertex Cover. This is the special case of Vertex Cover where the input graph is planar, and it itself can be proved NP-hard by reduction from Planar 3Sat. (Planar 3Sat is, similarly, the special case of 3Sat where the input graph is planar. Proved NP-hard by reduction from normal 3Sat, and it itself is used to prove that various games are NP-hard, such as Super Mario Bros, Super Mario Bros 3, and Super Mario World.)

This reduction was first done by Garey and Johnson in 1977. I'm currently trying to find the full details of their proof, but these lecture notes provide a general overview.


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.