2025-11-21T03:46:15.611457

A Faster Randomized Algorithm for Vertex Cover: An Automated Approach

Clinch, Gaspers, He et al.

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)$.

academic

A Faster Randomized Algorithm for Vertex Cover: An Automated Approach

基本信息

论文ID: 2510.09027
标题: A Faster Randomized Algorithm for Vertex Cover: An Automated Approach
作者: Katie Clinch (University of Queensland), Serge Gaspers (UNSW Sydney), Tao Zixu He (University of Massachusetts Amherst), Simon Mackenzie (UNSW Sydney), Tiankuang Zhang (UNSW Sydney)
分类: cs.DS (Data Structures and Algorithms), cs.CC (Computational Complexity)
发表时间: 2025年
论文链接: https://arxiv.org/abs/2510.09027

摘要

本文针对顶点覆盖问题引入了两项分支算法设计和分析的新技术。首先，提出了一种通过系统性局部结构案例分析自动生成分支规则的方法。其次，开发了一种使用Measure & Conquer方法分析随机分支算法的新技术，在制定分支规则方面提供了更大的灵活性。通过结合这些创新与其他技术，获得了在有界度图（最高度数为6）和一般图上顶点覆盖问题的最快已知随机算法。例如，算法在三次图上的运行时间为 $O^*(1.07625^n)$ 和 $O^*(1.13132^k)$ ，在最大度数为4的图上达到 $O^*(1.13735^n)$ 和 $O^*(1.21103^k)$ 的运行时间，在一般图上达到 $O^*(1.25281^k)$ 。

研究背景与动机

问题重要性

顶点覆盖问题是计算机科学中最经典的NP完全问题之一，已被研究超过50年。给定图 $G = (V, E)$ 和整数 $k$ ，需要判断是否存在大小至多为 $k$ 的顶点子集 $C \subseteq V$ 覆盖所有边。该问题在理论计算机科学和实际应用中都具有重要意义。

现有方法局限性

手工设计的局限性：精确分支算法虽然是解决NP困难问题最有效的工具之一，但仍主要依赖手工制作，每个新问题都需要定制的案例分析和精心调整的测度。
可移植性差：这种手工过程限制了算法的可移植性并减缓了研究进展。
随机化分析不足：现有的Measure & Conquer方法主要用于确定性算法，缺乏对随机分支算法的系统分析方法。

研究动机

本文认为分支算法设计中的大部分工作可以自动化，提出了一个框架来：

系统性地探索局部配置
通过合并等价类来简化搜索
通过求解直接优化测度进展的LP/ILP公式生成高质量的确定性或随机分支规则

核心贡献

随机化Measure & Conquer：将Measure & Conquer扩展到分析随机算法的运行时间，使M&C能够有效处理概率分支规则。
基于LP/ILP的自动规则生成：引入了一个新颖的框架，将规则选择和权重分配作为直接最大化测度减少的优化问题，自然支持确定性和随机规则。
顶点覆盖问题的改进运行时间：生成的算法改进了一般图和多种有界度情况下的最佳已知参数化界限，包括：
- 三次图： $O^*(1.07625^n)$ 和 $O^*(1.13132^k)$
- 度数4图： $O^*(1.13735^n)$ 和 $O^*(1.21103^k)$
- 一般图： $O^*(1.25281^k)$

方法详解

任务定义

顶点覆盖问题：给定无向图 $G = (V, E)$ 和非负整数 $k$ ，判断是否存在顶点子集 $C \subseteq V$ 且 $|C| \leq k$ ，使得 $C$ 覆盖所有边（即每条边至少有一个端点在 $C$ 中）。

核心技术框架

1. 随机化Measure & Conquer

引理2：设 $A_r$ 是决策问题 $\Pi$ 的随机分支算法， $\mu(\cdot)$ 是 $\Pi$ 实例的非负测度。对于任何实例 $I$ ， $A_r$ 要么在 $\mu(I) = 0$ 时以常数时间求解 $I$ ，要么将 $I$ 归约为带相应权重 $w_1, \ldots, w_k$ 的子实例 $I_1, \ldots, I_k$ 。

关键约束条件： $\sum_{i=1}^k w_i \cdot 2^{\mu(I_i)} \leq 2^{\mu(I)}$

子实例 $I_i$ 被随机选择的概率至少为 $w_i \cdot 2^{\mu(I_i)-\mu(I)}$ 。

2. 局部配置和扩展覆盖

定义3（局部配置）：顶点覆盖问题的局部配置定义为元组 $L = (H, D)$ ，其中 $H = (V, E)$ 是图， $D$ 是将每个顶点映射到其关联的不完整边数的函数。

算法2（扩展算法）：

选择具有最小度数和最少不完整边的边界顶点 $v$
对每个 $u_i \in \delta(L) \setminus \{v\}$ ，创建连接 $v-u_i$ 的新局部配置
为每个 $i \in \{1, \ldots, \Delta\}$ ，添加度数为 $i$ 的新顶点 $u$ 并连接到 $v$

3. 测度设计

使用测度： $\mu = \alpha k + \beta_1 n_1 + \beta_2 n_2 + \beta_3 n_3$

其中 $k$ 是顶点覆盖大小， $n_i$ 表示度数为 $i$ 的顶点数， $\alpha, \beta_1, \beta_2, \beta_3$ 是权重。

约束条件：

对于参数 $n$ 的算法： $\alpha = 0$ 且 $\beta_3 \geq 0$ ，得到 $0 \leq \frac{3\beta_1}{4} \leq \frac{3\beta_2}{4} \leq \beta_3$
对于参数 $k$ 的算法： $\beta_i \leq 0$ （ $i \in \{1,2\}$ ）且 $\beta_3 = 0$

4. 分支规则生成

线性规划公式： $\min_w \sum_{b_i \in B} w_i \cdot \text{cost}(L, b_i)$ $\text{s.t. } \forall R_i \in \mathcal{R} \sum_{b_j \in B: R_i \in EB(L,b_j,\mathcal{R})} w_j \geq 1$ $\forall b_i \in B: w_i \in [0,1]$

技术创新点

边中心扩展：与之前逐顶点扩展不同，采用逐边扩展配置，显著减少候选配置数量。
冗余控制：通过实例空间分区和同构局部配置合并消除重复，避免频繁子图同构查询的开销。
统一优化框架：将规则选择和权重分配表述为单一LP/ILP优化问题，直接最大化测度进展，无缝支持随机分支。

实验设置

测试环境

使用两个测度： $\mu_1 = 0.106n_3$ （参数 $n$ ）和 $\mu_2 = 0.178k - 0.0445n_1 - 0.089n_2$ （参数 $k$ ）
将三次图的实例空间划分为19个子空间进行优化
图同构检测使用Nauty库，线性规划求解器使用ALGLIB

简化规则

实现了5个简化规则：

孤立顶点规则
度数1顶点规则
度数2三角形规则
度数2链规则
交替环规则

对比基准

与以下最新结果对比：

三次图：Xiao & Nagamochi的 $O^*(1.08351^n)$ 和 $O^*(1.14416^k)$
度数4图：Xiao & Nagamochi的 $O^*(1.13760^n)$ 和 $O^*(1.21131^k)$
一般图：Harris & Narayanaswamy的 $O^*(1.25284^k)$

实验结果

主要结果

最大度数	参数	新界限	之前界限
∆ ≤ 3	n	$O^*(1.07625^n)$	$O^*(1.08351^n)$
	k	$O^*(1.13132^k)$	$O^*(1.14416^k)$
∆ ≤ 4	n	$O^*(1.13735^n)$	$O^*(1.13760^n)$
	k	$O^*(1.21103^k)$	$O^*(1.21131^k)$
∆ ≤ 5	k	$O^*(1.24382^k)$	$O^*(1.24394^k)$
∆ ≤ 6	k	$O^*(1.25210^k)$	$O^*(1.25214^k)$
一般图	k	$O^*(1.25281^k)$	$O^*(1.25284^k)$