2025-11-21T08:22:15.372442

An efficient algorithm for \textsc{$\mathcal{F}$-subgraph-free Edge Deletion} on graphs having a product structure

An, Im, Kim et al.

Given a family $\mathcal{F}$ of graphs, a graph is \emph{$\mathcal{F}$-subgraph-free} if it has no subgraph isomorphic to a member of $\mathcal{F}$. We present a fixed-parameter linear-time algorithm that decides whether a planar graph can be made $\mathcal{F}$-subgraph-free by deleting at most $k$ vertices or $k$ edges, where the parameters are $k$, $\lvert \mathcal{F} \rvert$, and the maximum number of vertices in a member of $\mathcal{F}$. The running time of our algorithm is double-exponential in the parameters, which is faster than the algorithm obtained by applying the first-order model checking result for graphs of bounded twin-width. To obtain this result, we develop a unified framework for designing algorithms for this problem on graphs with a ``product structure.'' Using this framework, we also design algorithms for other graph classes that generalize planar graphs. Specifically, the problem admits a fixed-parameter linear time algorithm on disk graphs of bounded local radius, and a fixed-parameter almost-linear time algorithm on graphs of bounded genus. Finally, we show that our result gives a tight fixed-parameter algorithm in the following sense: Even when $\mathcal{F}$ consists of a single graph $F$ and the input is restricted to planar graphs, it is unlikely to drop any parameters $k$ and $\lvert V(F) \rvert$ while preserving fixed-parameter tractability, unless the Exponential-Time Hypothesis fails.

academic

積構造を持つグラフ上のF-部分グラフ無関辺削除の効率的アルゴリズム

基本情報

論文ID: 2510.14674
タイトル: An efficient algorithm for F-subgraph-free Edge Deletion on graphs having a product structure
著者: Shinwoo An (Bar-Ilan University)、Seonghyuk Im (KAIST & IBS)、Seokbeom Kim (KAIST & IBS)、Myounghwan Lee (Hanyang University)
分類: cs.DM (離散数学)、cs.DS (データ構造とアルゴリズム)、math.CO (組合数学)
発表日: 2025年10月17日 (arXiv プレプリント)
論文リンク: https://arxiv.org/abs/2510.14674

概要

グラフ族 $\mathcal{F}$ が与えられたとき、 $\mathcal{F}$ 中のいかなるメンバーと同型な部分グラフも含まないグラフを $\mathcal{F}$ -部分グラフ無関と呼ぶ。本論文は、平面グラフが最大 $k$ 本の辺を削除することで $\mathcal{F}$ -部分グラフ無関になるかを判定する固定パラメータ線形時間アルゴリズムを提案する。パラメータは $k$ 、 $|\mathcal{F}|$ 、および $\mathcal{F}$ 中のグラフの最大頂点数である。アルゴリズムの実行時間はパラメータに関して二重指数的であり、有界twin-width グラフの一階モデル検査結果を適用した場合のアルゴリズムより高速である。

研究背景と動機

問題定義

F-部分グラフ無関辺削除 問題は以下のように定義される：

入力: グラフ $G$ と非負整数 $k$
タスク: 大きさが最大 $k$ の辺集合 $S \subseteq E(G)$ が存在し、 $G - S$ が $\mathcal{F}$ 中のいかなるグラフも部分グラフとして含まないかを判定する

研究の意義

実用的価値: 本問題は現実世界の多くのシナリオをモデル化できる：
- 動物疾病伝播制御：グラフは農場間の伝送ネットワークを表し、目標は少数の接続を禁止することで疫病を制御する
- ネットワークセキュリティ：少数の辺を削除することで悪意あるネットワーク構造を破壊する
理論的重要性:
- 辺二部化 (Edge Bipartization) およびフィードバック弧集合 (Feedback Arc Set) などの古典的問題を含む
- グラフ修正問題の重要な特殊例である

既存手法の限界

複雑性の障壁: $\mathcal{F}$ が単一のグラフ $F$ のみを含む場合でも、多くのグラフ $F$ に対して本問題はNP完全である
パラメータ化複雑性:
- 解のサイズ $k$ のみをパラメータとする場合、問題はW1完全問題を含む（クリークと独立集合など）
- 木幅のみをパラメータとする場合、問題はW2困難である
実行時間: 既存のtwin-width法は塔型依存の実行時間を生成する

核心的貢献

統一的アルゴリズムフレームワーク: グラフ積構造に基づく統一フレームワークを開発し、積構造を持つグラフクラスに適用可能
効率的アルゴリズム:
- 平面グラフ上の固定パラメータ線形時間アルゴリズム（時間計算量 $2^{O(|\mathcal{F}|^2kr^3)} \cdot n$ ）
- 有界局所半径円盤グラフ上の固定パラメータ線形時間アルゴリズム
- 有界種数グラフ上の固定パラメータ準線形時間アルゴリズム
積構造理論の拡張: 有界局所半径の円盤グラフが積構造を持つことを証明
タイトネス結果: 指数時間仮説が成立しない限り、アルゴリズムはパラメータ依存性の観点から最適であることを証明

方法の詳細

コア技術フレームワーク

グラフ積構造

2つのグラフ $G$ と $H$ に対して、強積 $G \boxtimes H$ は以下のように定義される：

頂点集合： $V(G) \times V(H)$
辺集合：2つの頂点 $(u,v)$ $(u, v)$ と $(u',v')$ $(u^{'}, v^{'})$ が隣接するのは以下の条件のいずれかを満たす場合：
- $u = u'$ かつ $vv' \in E(H)$
- $v = v'$ かつ $uu' \in E(G)$
- $uu' \in E(G)$ かつ $vv' \in E(H)$

グラフクラス $\mathcal{C}$ 中のすべてのグラフが、木幅が最大 $w$ のグラフ $H$ と路 $P$ の強積の部分グラフである場合、 $\mathcal{C}$ は積構造を持つと言う。

主要アルゴリズムフレームワーク（定理1.5）

入力:

グラフ $G$ （ $n$ 個の頂点）
グラフ $H$ （木幅 $\leq w$ ）と路 $P$
$G$ から $H \boxtimes P$ への埋め込み

出力: $G$ 上のF-部分グラフ無関辺削除問題の解

時間計算量: $2^{O(|\mathcal{F}|^2kr^3w)} \cdot n$

アルゴリズム設計

層化技術

層の定義: 路 $P$ の頂点を $[ℓ]$ とラベル付けし、第 $i$ 層を $V_i = (V(H) \times \{i\}) \cap V(G)$ と定義
区間分割: 各整数 $j$ に対して、 $I_j = [3(j-1)r+1, 3jr]$ と $V_{I_j} = \bigcup_{i \in I_j} V_i$ を定義