0
$\begingroup$

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.

$\endgroup$
3
  • $\begingroup$ Have you tried to reduce from (ordinary) vertex cover? $\endgroup$
    – D.W.
    May 28, 2018 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, 2018 at 22:36
  • 1
    $\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, 2018 at 20:06

2 Answers 2

1
$\begingroup$

(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.

$\endgroup$
1
$\begingroup$

Consider the following polynomial-time Karp reduction.

Given an input to VERTEX COVER: [graph G, integer k]

Construct a new graph G* by adding a single new vertex v* to G. Then connect v* to all other vertices.

The input [graph G*, integer k+1] is a positive instance of CONNECTED VERTEX COVER if and only if the input [graph G, integer k] is a positive instance of VERTEX COVER.

Backwards direction: Any vertex cover (size k) in G gives a connected vertex cover (size k+1) in G* by also including v*.

Forwards direction: v* has an edge to every other vertex in G*. So any vertex cover in G* must either include every vertex in G or must include v* (otherwise it wouldn't cover some of the edges from v*). Suppose a connected vertex cover (size k+1) of G* does include v*, then removing v* clearly gives a vertex cover (size k) (not necessarily connected) of G=G-{v}. Suppose a connected vertex cover (size k+1) of G* includes all vertices of G. Note every edge has two endpoints so we can discard any one vertex and still have a vertex cover (size k) of G

VERTEX COVER ≤ CONNECTED VERTEX COVER

$\endgroup$
3
  • $\begingroup$ I don't see the second direction (CVC of size $k+1 \implies$ VC of size $k$) yet. What if the CVC doesn't use $v^*$? It's not clear that we can just pick an arbitrary vertex, delete it, and still have a VC for $G$. $\endgroup$ May 31, 2021 at 22:10
  • 1
    $\begingroup$ v* has an edge to every other vertex in G*. So any vertex cover in G* must either include every vertex in G or must include v* (otherwise it wouldn't cover some of the edges from v*). Suppose a connected vertex cover (size k+1) of G* does include v*, then removing v* clearly gives a vertex cover (size k) (not necessarily connected) of G=G*-{v*}. Suppose a connected vertex cover (size k+1) of G* includes all vertices of G. Note every edge has two endpoints so we can discard any one vertex and still have a vertex cover (size k) of G. $\endgroup$
    – Samuel
    Jun 1, 2021 at 10:05
  • $\begingroup$ Thanks, that looks good to me -- please add it to your answer. $\endgroup$ Jun 1, 2021 at 12:18

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.