# Minimum vertex cover on k-regular graphs, for fixed k>2 NP-hard proof?

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): @R B gave a construction below!

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:

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

For example, if your initial cubic graph is:

Then the resulting $4$-regular graph is:

And the 5-regular graph would be:

• 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 Jan 19 '15 at 2:52
• @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 Jan 19 '15 at 6:39
• 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 Jan 19 '15 at 13:33
• @PageWizard - I added examples. You should be able to generalize it from here.. – R B Jan 19 '15 at 15:03
• Perfect, thank you so much :)! I really appreciate the examples. – PageWizard Jan 19 '15 at 15:45

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

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.

• 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 Jan 18 '15 at 15:02
• @PageWizard - well, another partial answer here :). – R B Jan 18 '15 at 15:49