4
$\begingroup$

Our problem is: Given an undirected graph, does it have a vertex cover consisting of $k$ vertices?

A vertex included in this vertex cover variant will cover every edge incident to it and every edge incident to some edge incident to it. Hence, we call this variant a vertex cover with covering radius 2.

What is the computational complexity of this problem?

$\endgroup$
5
$\begingroup$

It is still NP-complete. It is easy to see it is in NP. To prove its NP-completeness, we reduce the standard vertex cover problem to this problem.

Given an instance $G=(V,E)$ of vertex cover problem, we construct a new graph $G'$ based on $G$ as follows.

  1. For each edge $(u,v)\in E$, split it into three edges $(u,u_v)$, $(u_v, v_u)$, $(v_u,v)$ where $u_v$ and $v_u$ are newly added vertices.

  2. For each vertex $v\in V$, add three edges $(v,v_1),(v_1,v_2),(v_2,v_3)$, where $v_1,v_2$ and $v_3$ are newly added vertices.

Now we assert that $G$ has a vertex cover of size $k$ if and only if $G'$ has a vertex cover with radius 2 and of size $k+|V|$.

If $G$ has a vertex cover of size $k$, then this vertex cover as well as $v_1$'s for all $v\in V$ makes up a vertex cover of $G'$ with radius 2.

On the other hand, assume $G'$ has a vertex cover $C'$ with radius 2 and of size $k+|V|$. Note for each $v\in V$, since $(v_2,v_3)$ is covered, at least one of $v_1,v_2$ and $v_3$ should be included in $C'$. We can assume $v_1$ is always included and $v_2,v_3$ are never included in $C'$. Now the rest $k$ vertices are of either the form $u$ or the form $u_v$ where $u,v\in V$. Let $$C=\{u\in V\mid u\in C'\text{ or }u_v\in C'\text{ for some }v\}.$$

Note for each $(u,v)\in E$, $(u_v,v_u)$ is covered by $C'$, then at least one of $u, u_v, v_u, v$ is included in $C'$, which means either $u$ or $v$ is inclulded in $C$. Hence $C$ is a vertex cover of $G$, which has size no more than $k$.

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