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

An efficient algorithm for F-subgraph-free Edge Deletion on graphs having a product structure

基本信息

论文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-subgraph-free Edge Deletion 问题定义如下：

输入: 图 $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$ ）
- 有界局部半径圆盘图上的固定参数线性时间算法
- 有界亏格图上的固定参数近线性时间算法
乘积结构理论扩展: 证明了有界局部半径的圆盘图具有乘积结构
紧致性结果: 证明了算法在参数依赖性方面是最优的，除非指数时间假设失效

顶点集： $V(G) \times V(H)$
边集：两个顶点 $(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$ 上 $\mathcal{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$