2022/05/16 by Harris, David G., Narayanaswamy, N. S. · 5 citations
#Combinatorics (math.CO) #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #FOS: Mathematics
paper · doi:10.48550/arxiv.2205.08022
We describe a new algorithm for vertex cover with runtime O^*(1.25284k), where k is the size of the desired solution and O^* hides polynomial factors in the input size. This improves over previous runtime of O^*(1.2738k) due to Chen, Kanj, & Xia (2010) standing for more than a decade. The key to our algorithm is to use a potential function which simultaneously tracks k as well as the optimal value λ of the vertex cover LP relaxation. This approach also allows us to make use of prior algorithms for Maximum Independent Set in bounded-degree graphs and Above-Guarantee Vertex Cover. The main step in the algorithm is to branch on high-degree vertices, while ensuring that both k and μ= k - λ are decreased at each step. There can be local obstructions in the graph that prevent μ from decreasing in this process; we develop a number of novel branching steps to handle these situations.