Hardness of approximating the Minimum Vertex Cover problem for 4-regular graphs
Wenbi Chen · Journal of Guangzhou University · 2014
In this paper,we show that it is hard to approximate the Minimum Vertex Cover for 4-regular graphs within some constant factor. Similarly,the result is also correct for 5-regular graphs,6-regular graphs and so on. It is known that approximating the Minimum Vertex Cover problem for 3-regular graphs within some constant factor is NP-hard. We extend the result to 4-regular graphs. We use K-reductions to prove this result. We give a K-reduction from the Minimum Vertex Cover of 3-regular graphs to that of 4-regular graphs.