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

より高速なランダム化頂点被覆アルゴリズム：自動化アプローチ

基本情報

論文ID: 2510.09027
タイトル: A Faster Randomized Algorithm for Vertex Cover: An Automated Approach
著者: Katie Clinch (クイーンズランド大学)、Serge Gaspers (UNSW シドニー)、Tao Zixu He (マサチューセッツ大学アマースト校)、Simon Mackenzie (UNSW シドニー)、Tiankuang Zhang (UNSW シドニー)
分類: cs.DS (データ構造とアルゴリズム)、cs.CC (計算複雑性)
発表時期: 2025年
論文リンク: https://arxiv.org/abs/2510.09027

要旨

本論文は頂点被覆問題に対して、分枝アルゴリズムの設計と分析における2つの新しい技術を導入している。第一に、局所構造の体系的なケース分析を通じて分枝規則を自動生成する方法を提案している。第二に、Measure & Conquerメソッドを用いてランダム化分枝アルゴリズムを分析する新しい技術を開発し、分枝規則の策定においてより大きな柔軟性を提供している。これらの革新と他の技術を組み合わせることにより、有界次数グラフ（最大次数6まで）および一般グラフ上の頂点被覆問題に対する最速の既知ランダム化アルゴリズムを得た。例えば、3次グラフ上でのアルゴリズムの実行時間は $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ベースの自動規則生成：規則選択と重み付け割り当てを測度減少を直接最大化する最適化問題として導入する新しいフレームワークを提案し、決定性規則とランダム化規則を自然にサポートしている。
頂点被覆問題の改善された実行時間：生成されたアルゴリズムは一般グラフと複数の有界次数の場合における最良の既知パラメータ化界を改善し、以下を含む：
- 3次グラフ： $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$ 内に少なくとも1つの端点を持つ）ものが存在するかどうかを判定する。

核心的技術フレームワーク

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最適化問題として定式化し、測度の進展を直接最大化し、ランダム化分枝をシームレスにサポートしている。

実験設定

テスト環境

2つの測度を使用： $\mu_1 = 0.106n_3$ （パラメータ $n$ ）および $\mu_2 = 0.178k - 0.0445n_1 - 0.089n_2$ （パラメータ $k$ ）
3次グラフのインスタンス空間を19の部分空間に分割して最適化
グラフ同型検出にはNautyライブラリを使用し、線形計画法ソルバーにはALGLIBを使用

簡略化規則

5つの簡略化規則を実装：

孤立頂点規則
次数1頂点規則
次数2三角形規則
次数2チェーン規則
交互サイクル規則

比較ベンチマーク

以下の最新結果と比較：

3次グラフ：Xiaoと長橋の $O^*(1.08351^n)$ および $O^*(1.14416^k)$
次数4グラフ：Xiaoと長橋の $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)$