A Faster Randomized Algorithm for Vertex Cover: An Automated Approach

This work introduces two techniques for the design and analysis of branching algorithms, illustrated through the case study of the Vertex Cover problem. First, we present a method for automatically generating branching rules through a systematic case analysis of local structures. Second, we develop a new technique for analyzing randomized branching algorithms using the Measure & Conquer method, offering greater flexibility in formulating branching rules. By combining these innovations with additional techniques, we obtain the fastest known randomized algorithms in different parameters for the Vertex Cover problem on graphs with bounded degree (up to 6) and on general graphs. For example, our algorithm solves Vertex Cover on subcubic graphs in $O^*(1.07625^n)$ time and $O^*(1.13132^k)$ time, respectively. For graphs with maximum degree 4, we achieve running times of $O^*(1.13735^n)$ and $O^*(1.21103^k)$, while for general graphs we achieve $O^*(1.25281^k)$.