A Note on Vertex Cover in Graphs with Maximum Degree 3

摘要

We show that the k-Vertex Cover problem in degree-3 graphs can be solved in O~*(1.1616~k) time, which improves previous results of O~*(1.1940~k) by Chen, Kanj and Xia and O~*(1.1864~k) by Razgon. In this paper, we will present a new way to analyze algorithms for the problem. We use r = k - 2/5n to measure the size of the search tree, and then get a simple O(1.6651~(k-2/5n_0)-time algorithm, where no is the number of vertices with degree ≥ 2 in the graph. Combining this result with fast algorithms for the Maximum Independent Set problem in degree-3 graphs, we improve the upper bound for the k-Vertex Cover problem in degree-3 graphs.