I am aware that the minimum (cardinality) vertex cover problem on cubic graphs (i.e., 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.)
My goal is to locate a paper that addresses the problem for any k>2 (if it exists), but any details would be helpful.
Note: I also asked this question on CSTheory StackExchange. http://cstheory.stackexchange.com/questions/29175/minimum-vertex-cover-on-k-regular-graphs-for-fixed-k2-np-hard-proof
Thank you so much!
I see that there is a reduction proof on the CSTheory StackExchange website already. But if it is a reference that you need, here it is:
Fricke, G. H., Hedetniemi, S. T., Jacobs, D. P.,
Independence and irredundance in k-regular graphs.
Ars Combin. 49 (1998), 271–279.
Summary from MathSciNet: "We show that for each fixed k≥3, the INDEPENDENT SET problem is NP-complete for the class of k-regular graphs. Several other decision problems, including IRREDUNDANT SET, are also NP-complete for each class of k-regular graphs, for k≥6.''
Now, if the summary is correct, the authors prove that the decision version of the independent set problem is NP-complete for the class of k-regular graphs. Therefore, the optimization problem of finding the maximal independent set is np-hard for the same class. And of course, the minumum vertex cover is the complement of the max independent set. Hope this helps.
Thank you so much Petar! Yes, this will help me as well. I really appreciate the source.
- Badges
- Science topic
- Similar topics
- Mathematical Sciences
- Graphs