<p>By adding a small ($O(k)$) sized graph to each vertex you could reduce $VC$ of size $m$ in a 3-regular graph $G$ to $VC$ of size $m+2k|V|$ in a $k-regular$ graph.</p>

<hr>

<p>Here is a reduction for 5-regular graphs, and I believe you can easily generalize it for every $(2k+1)$-regular graphs, for every integer $k$, and perhaps some trickery would allow similar construction for $2k$-regular graphs;</p>

<p>Consider the graph $H$ in the photo:</p>

<p><img src="https://i.sstatic.net/2aqCn.png" alt="enter image description here"></p>

<p>(all vertices has degree 5, except for the blue vertex).</p>

<p>For every vertex $v$ in the 3-regular graph $G$, create two copies of $H$ and connect $v$ to their blue vertices.</p>

<p>It is easy to see that regardless of whether $v$ was selected for the cover, you have to include at least $5$ vertices from $H_v$ in the cover (you can take the blue and green ones).</p>

<p>Hence every vertex cover of size $m$ in $G$ corresponds to a $m+10|V|$ sized cover in the new 5-regular graph, and vice versa.</p>

<hr>

<p>EDIT:</p>

<p>Similar trick could be applied to get $2k$-regular graphs as well. Consider for example the following reduction from 3-regular to 4-regular graphs;</p>

<p>Partition the graph vertices into pairs (duplicate the graph if the number of vertices is odd), and for every pair $u,v$ connect each to a blue vertex in the following structure:</p>

<p><img src="https://i.sstatic.net/snZie.png" alt="enter image description here"></p>

<hr>

<p>For example, if your initial cubic graph is:</p>

<p><img src="https://i.sstatic.net/3EI2F.png" alt="enter image description here"></p>

<p>Then the resulting $4$-regular graph is:</p>

<p><img src="https://i.sstatic.net/CxyOW.png" alt="enter image description here"></p>

<p>And the 5-regular graph would be:</p>

<p><img src="https://i.sstatic.net/Wow2o.png" alt="enter image description here"></p>

CC BY-SA 3.0
2015-01-19T02:52:45.937Z
I noticed one flaw in these constructions.  As you say, the blue vertex (say when we consider 5-regular), the blue vertex doesn't have degree 5 (it has 4), so it isn't a 5-regular graph (every vertex needs degree 5).  Though I need to tinker with the even case some more, maybe one could connect an edge between the two blue vertices to ensure it is a 4-regular graph?
PageWizard
CC BY-SA 3.0
2015-01-19T06:39:13.300Z
@PageWizard - that's on purpose :). It's of degree $k-1$ in $H$, but then we connect it to a graph vertex to complete the degree..
R B
CC BY-SA 3.0
2015-01-19T13:33:38.567Z
I think I get what you're saying, but I could be wrong.  If possible, can you provide an example that starts with a cubic graph G, then proceeds through to construct H, and finally the k-regular graph (for each case, if possible)?  It would make it a bit more clearer.
PageWizard
CC BY-SA 3.0
2015-01-19T15:03:57.890Z
@PageWizard - I added examples. You should be able to generalize it from here..
R B
CC BY-SA 3.0
2015-01-19T15:45:17.623Z
Perfect, thank you so much :)!  I really appreciate the examples.
PageWizard
CC BY-SA 3.0
2015-01-18T15:45:13.567Z
2015-01-19T15:03:01.543Z
2015-01-19T15:03:01.543Z
R B
<p>Fleischner, Sabidussi and Sarvanov proved in 2010 that independent set (and hence also vertex cover) is NP-complete even in 4-regular Hamiltonian graphs.</p>

<p>Herbert Fleischner, Gert Sabidussi, Vladimir I. Sarvanov: 
Maximum independent sets in 3- and 4-regular Hamiltonian graphs. 
Discrete Mathematics 310: 2742-2749 (2010)
<a href="http://www.sciencedirect.com/science/article/pii/S0012365X10001974">http://www.sciencedirect.com/science/article/pii/S0012365X10001974</a></p>

CC BY-SA 3.0
2015-01-18T15:41:14.390Z
2015-01-18T15:41:14.390Z
Gamow
<p>I think you could show that for any $k$, $3k$-regular graphs (e.g. 6-regular) the problem is NP-hard by a reduction from cubic graphs:</p>

<p>Let $G=(V,E)$ be a 3-regular graph, then construct $k$ copies of $G$, and connect them:
$$G_k=(\cup\{V_i|i\in [k]\}, \cup \{E_{i,j}\ | i,j\in [k] \})$$</p>

<p>Where $$V_i=\{v_i|v\in V\}, E_{i,j}=\{(u_i,v_j)|(u,v)\in E\}$$</p>

<p>Now it shouldn't be hard to argue that if a vertex set $H\subseteq V$ is a vertex cover for $G$, then  $\cup \{H_i|i\in [k]\}$ is a vertex cover for $G_k$, and the smallest VC for $G_k$ can't be smaller than $k$ times the smallest VC for $G$, every $V_i$ has to be properly covered.</p>

CC BY-SA 3.0
2015-01-18T15:02:33.203Z
Ahh yes!  Thank you so much.  All that remain are the other k-regular graphs (e.g., 4-regular, 5-regular, 7-regular,...) when it isn't a multiple of 3 that is 3 or greater.  This is at least a step in the right direction. :)
PageWizard
CC BY-SA 3.0
2015-01-18T15:49:37.407Z
@PageWizard - well, another partial answer [here](http://cstheory.stackexchange.com/questions/29175/minimum-vertex-cover-on-k-regular-graphs-for-fixed-k2-np-hard-proof/29188#29188) :).
R B
CC BY-SA 3.0
2015-01-18T10:23:10.773Z
2015-01-18T12:38:58.137Z
2015-01-18T12:38:58.137Z
R B
<p>Good Evening!</p>

<p>I am aware that the minimum (cardinality) vertex cover problem on cubic graphs ($3$-regular) graphs is $NP$-hard.  <strong>Say positive integer $k&gt;2$ is fixed</strong>. Has there been any computational complexity proof (aside from the $3$-regular result, note this would be $k=3$,) that shows the minimum (cardinality) vertex cover problem on $k$-regular graphs is $NP$-hard (e.g., $4$-regular)?  Since $k$ is fixed, you aren't guaranteed the cubic graph instances needed to show the classic result I mentioned above.  </p>

<p>Note that this problem would be straightforward to see is $NP$-hard from the result I mentioned at the start if we were to state that this were for any regular graph (since $3$-regular is a special case), we don't get that when $k$ is fixed. </p>

<p>Does anybody know of any papers that address the computational complexity of minimum (cardinality) vertex cover on a $k$-regular graph, when $k$ is fixed/constant?  I have been having difficulties trying to find papers that address this (in the slew of documents that cover the classic result of minimum (cardinality) vertex cover on cubic graphs being $NP$-hard.) </p>

<p>Thank you so much!</p>

<p>EDIT (again): @R B gave a construction below!</p>

<cc.complexity-theory><graph-theory><graph-algorithms><np-hardness>
Minimum vertex cover on k-regular graphs, for fixed k>2 NP-hard proof?
PageWizard
# Minimum vertex cover on k-regular graphs, for fixed k>2 NP-hard proof?

(Asked by: username_0 on 2015-01-18)

Good Evening!

I am aware that the minimum (cardinality) vertex cover problem on cubic graphs ($3$-regular) graphs is $NP$-hard. **Say positive integer $k>2$ is fixed**. Has there been any computational complexity proof (aside from the $3$-regular result, note this would be $k=3$,) that shows the minimum (cardinality) vertex cover problem on $k$-regular graphs is $NP$-hard (e.g., $4$-regular)? Since $k$ is fixed, you aren't guaranteed the cubic graph instances needed to show the classic result I mentioned above.

Note that this problem would be straightforward to see is $NP$-hard from the result I mentioned at the start if we were to state that this were for any regular graph (since $3$-regular is a special case), we don't get that when $k$ is fixed.

Does anybody know of any papers that address the computational complexity of minimum (cardinality) vertex cover on a $k$-regular graph, when $k$ is fixed/constant? I have been having difficulties trying to find papers that address this (in the slew of documents that cover the classic result of minimum (cardinality) vertex cover on cubic graphs being $NP$-hard.)

Thank you so much!

EDIT (again): @username_1 gave a construction below!

**Tags:** cc.complexity-theory, graph-theory, graph-algorithms, np-hardness


---

## 3 answers

### Answer by username_1 on 2015-01-18. Score: 7 | Accepted answer

By adding a small ($O(k)$) sized graph to each vertex you could reduce $VC$ of size $m$ in a 3-regular graph $G$ to $VC$ of size $m+2k|V|$ in a $k-regular$ graph.

---

Here is a reduction for 5-regular graphs, and I believe you can easily generalize it for every $(2k+1)$-regular graphs, for every integer $k$, and perhaps some trickery would allow similar construction for $2k$-regular graphs;

Consider the graph $H$ in the photo:

![enter image description here](https://i.sstatic.net/2aqCn.png)

(all vertices has degree 5, except for the blue vertex).

For every vertex $v$ in the 3-regular graph $G$, create two copies of $H$ and connect $v$ to their blue vertices.

It is easy to see that regardless of whether $v$ was selected for the cover, you have to include at least $5$ vertices from $H\_v$ in the cover (you can take the blue and green ones).

Hence every vertex cover of size $m$ in $G$ corresponds to a $m+10|V|$ sized cover in the new 5-regular graph, and vice versa.

---

EDIT:

Similar trick could be applied to get $2k$-regular graphs as well. Consider for example the following reduction from 3-regular to 4-regular graphs;

Partition the graph vertices into pairs (duplicate the graph if the number of vertices is odd), and for every pair $u,v$ connect each to a blue vertex in the following structure:

![enter image description here](https://i.sstatic.net/snZie.png)

---

For example, if your initial cubic graph is:

![enter image description here](https://i.sstatic.net/3EI2F.png)

Then the resulting $4$-regular graph is:

![enter image description here](https://i.sstatic.net/CxyOW.png)

And the 5-regular graph would be:

![enter image description here](https://i.sstatic.net/Wow2o.png)

> **Comments:**
> **username_0**: I noticed one flaw in these constructions.  As you say, the blue vertex (say when we consider 5-regular), the blue vertex doesn't have degree 5 (it has 4), so it isn't a 5-regular graph (every vertex needs degree 5).  Though I need to tinker with the even case some more, maybe one could connect an edge between the two blue vertices to ensure it is a 4-regular graph?  
> **username_1**: @username_0 - that's on purpose :). It's of degree $k-1$ in $H$, but then we connect it to a graph vertex to complete the degree..  
> **username_0**: I think I get what you're saying, but I could be wrong.  If possible, can you provide an example that starts with a cubic graph G, then proceeds through to construct H, and finally the k-regular graph (for each case, if possible)?  It would make it a bit more clearer.  
> **username_1**: @username_0 - I added examples. You should be able to generalize it from here..  
> **username_0**: Perfect, thank you so much :)!  I really appreciate the examples.  

---

### Answer by username_2 on 2015-01-18. Score: 6

Fleischner, Sabidussi and Sarvanov proved in 2010 that independent set (and hence also vertex cover) is NP-complete even in 4-regular Hamiltonian graphs.

Herbert Fleischner, Gert Sabidussi, Vladimir I. Sarvanov:
Maximum independent sets in 3- and 4-regular Hamiltonian graphs.
Discrete Mathematics 310: 2742-2749 (2010)
<http://www.sciencedirect.com/science/article/pii/S0012365X10001974>


---

### Answer by username_1 on 2015-01-18. Score: 4

I think you could show that for any $k$, $3k$-regular graphs (e.g. 6-regular) the problem is NP-hard by a reduction from cubic graphs:

Let $G=(V,E)$ be a 3-regular graph, then construct $k$ copies of $G$, and connect them:
$$G\_k=(\cup\{V\_i|i\in [k]\}, \cup \{E\_{i,j}\ | i,j\in [k] \})$$

Where $$V\_i=\{v\_i|v\in V\}, E\_{i,j}=\{(u\_i,v\_j)|(u,v)\in E\}$$

Now it shouldn't be hard to argue that if a vertex set $H\subseteq V$ is a vertex cover for $G$, then $\cup \{H\_i|i\in [k]\}$ is a vertex cover for $G\_k$, and the smallest VC for $G\_k$ can't be smaller than $k$ times the smallest VC for $G$, every $V\_i$ has to be properly covered.

> **Comments:**
> **username_0**: Ahh yes!  Thank you so much.  All that remain are the other k-regular graphs (e.g., 4-regular, 5-regular, 7-regular,...) when it isn't a multiple of 3 that is 3 or greater.  This is at least a step in the right direction. :)  
> **username_1**: @username_0 - well, another partial answer [here](http://cstheory.stackexchange.com/questions/29175/minimum-vertex-cover-on-k-regular-graphs-for-fixed-k2-np-hard-proof/29188#29188) :).  

---

