A Faster Randomized Algorithm for Vertex Cover: An Automated Approach
Fuente:
arXiv
Saved in:
| Main Authors: | , , , , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866917001819062272 |
|---|---|
| author | Clinch, Katie Gaspers, Serge He, Tao Zixu Mackenzie, Simon Zhang, Tiankuang |
| author_facet | Clinch, Katie Gaspers, Serge He, Tao Zixu Mackenzie, Simon Zhang, Tiankuang |
| contents | 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)$. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2510_09027 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | A Faster Randomized Algorithm for Vertex Cover: An Automated Approach Clinch, Katie Gaspers, Serge He, Tao Zixu Mackenzie, Simon Zhang, Tiankuang Data Structures and Algorithms Computational Complexity 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)$. |
| title | A Faster Randomized Algorithm for Vertex Cover: An Automated Approach |
| topic | Data Structures and Algorithms Computational Complexity |
| url | https://arxiv.org/abs/2510.09027 |