5
$\begingroup$

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!

$\endgroup$
6
$\begingroup$

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

(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


For example, if your initial cubic graph is:

enter image description here

Then the resulting $4$-regular graph is:

enter image description here

And the 5-regular graph would be:

enter image description here

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

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

$\endgroup$
4
$\begingroup$

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.

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

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.