Improvement on Vertex Cover and Independent Set Problem for Low Degree Graphs

An exact algorithm to improve the upper bound of vertex cover and independent set problem for low degree graphs is presented. The algorithm constructs recurrence relations by concentrating on how many vertices be reduced then the NP hard structure of the problem is broken. With this idea, running time O (1 1033 n ) for minimum vertex cover problem on degree 3 graphs is proved. For parameterized vertex cover problem on degree 3 graphs, it also can be solved with running time O(kn +1.2174 k ). Using the algorithm to the maximum independent set problem on degree 3 graphs, the authors can get the running time O (1.1033 n ). All of the above results improve the previous best results.