带标签图收缩的参数化景观的更细致视图
《Journal of Computer and System Sciences》:A finer view of the parameterized landscape of labeled graph contractions
【字体:
大
中
小
】
时间:2026年10月02日
来源:Journal of Computer and System Sciences 1.4
编辑推荐:
## 摘要
我们研究有标签可收缩性问题(Labeled Contractibility),其输入由两个带顶点标签的图 $G$ 和 $H$ 组成,目标在于判定能否通过一系列边收缩操作从 $G$ 得到 $H$。Lafond 和 Marchand(2025)[42] 率先对该问题
## 摘要
我们研究有标签可收缩性问题(Labeled Contractibility),其输入由两个带顶点标签的图 $G$ 和 $H$ 组成,目标在于判定能否通过一系列边收缩操作从 $G$ 得到 $H$。Lafond 和 Marchand(2025)[42] 率先对该问题展开了参数化复杂度的研究,证明当以允许的收缩次数 $k$ 作为参数时,该问题为 W[1]-难的。他们还证明,当以 $G$ 的树宽 $\text{tw}$ 作为参数时,该问题是固定参数可处理的,并通过 Courcelle 定理的应用给出了一个对参数具有非初等依赖的算法。在本文工作中,我们提出了一个有标签可收缩性的构造性固定参数算法,运行时间为 $2^{O(\text{tw}^2)} \cdot |V(G)|^{O(1)}$。我们还证明,除非指数时间假设(ETH)不成立,否则不存在运行时间为 $2^{o(\text{tw}^2)} \cdot |V(G)|^{O(1)}$ 的算法。该结果将有标签可收缩性加入了一组极小的问题集合中——这些问题在 ETH 下其 $2^{\Theta(\text{tw}^2)}$ 的依赖关系是最优的。我们进一步强化了已有的难度结果,证明即使两个输入图的最大度数都有界,该问题仍然是 NP-难的。我们还研究了以 $(k + \delta(G))$ 作为参数的情形,其中 $\delta(G)$ 表示 $G$ 的退化度,并排除了亚指数时间算法的存在性。这回答了 Lafond 和 Marchand(2025)[42] 提出的关于亚指数固定参数可处理性的问题。我们另外给出了一个改进的 FPT 算法,运行时间为 $(\delta(H)+1)^k \cdot |V(G)|^{O(1)}$。最后,我们分析了有标签可收缩性的暴力算法,其运行时间为 $|V(H)|^{O(|V(G)|)}$,并证明该运行时间在 ETH 下是最优的。
## 引言
图修改问题是算法图论中的基础课题。$F$-$M$-修改问题的一个一般化表述如下:给定一个图 $G$ 和一个固定的允许修改操作集合 $M$(如顶点删除、边添加/删除或边收缩),能否使用至多 $k$ 个来自 $M$ 的操作将 $G$ 转化为图类 $F$ 中的图?
众所周知,当 $M$ 仅包含顶点或边删除操作时,$F$-$M$-修改问题对许多自然的图类 $F$ 是 NP-难的 [43], [54]。关于边收缩的难度结果最早由 Watanabe 等人 [53] 和 Asano 与 Hirata [4] 给出。值得注意的是,当 $M$ 仅包含顶点或边删除且 $F$ 为单元素集合时,该问题变得平凡可解;但对于边收缩则不然。事实上,Brouwer 和 Veldman [10] 证明,即使 $F$ 是一个包含四个顶点的图的单元素集合(例如路径 $P_4$ 或圈 $C_4$),该问题仍然是 NP-完全的。这一差异凸显了与顶点或边删除相比,边收缩所带来的算法复杂性的增加。
图修改问题在参数化复杂度的发展及关键算法技术的设计中发挥了核心作用。相关代表性工作包括 [8], [9], [12], [13], [14], [15], [18], [24], [25], [26], [28], [30]。Crespelle 等人 [19] 的综述提供了关于涉及边删除、编辑和补全的修改问题的深入讨论。
近年来的一系列论文研究了不同图类 $F$ 的 $F$-收缩的参数化复杂度,包括路径和树 [36]、树的一般化和限制 [1], [2]、仙人掌图 [41]、二部图 [35], [37]、平面图 [34]、网格 [50]、团 [11]、分裂图 [3]、弦图 [45]、二部完全图 [47],以及度数受限的图类 [5], [33], [51]。
近期,Lafond 和 Marchand [42] 率先在唯一标签图(即每个顶点具有不同标签)中研究边收缩问题的参数化复杂度。他们提出了以下问题:
> 参见第 2 节中定义 2.1 的正式定义。
他们还引入了一个推广版本,其动机来源于系统发生网络的应用 [46],系统发生网络是有根无环有向图,其带标签的叶子节点表示进化历史:
> 这个第二个问题与第一个问题密切相关。如 [42] 所示,$H$ 是 $G$ 的一个有标签收缩当且仅当存在 $G$ 和 $H$ 的公共收缩到一个具有至少 $|V(H)|$ 个顶点的带标签图 $H'$。这一等价性使得复杂度结果可以在两个问题之间相互转移。更多结果和应用参见同一文献 [42]。
Lafond 和 Marchand [42] 证明,当以自然参数 $k = |V(G) \setminus V(H)|$(即允许的边收缩次数)作为参数时,有标签可收缩性是 W[1]-难的。这促使了对结构参数的探索。他们通过调用 Courcelle 定理的一个变体 [27, 定理 11.73] 建立了该问题以输入图 $G$ 的树宽 $\text{tw}$ 为参数时存在固定参数可处理(FPT)算法的结果。然而,该方法对参数的依赖关系是非初等的。
我们的第一个贡献是一个构造性的动态规划算法,其运行时间对 $\text{tw}^2$ 是单指数的。我们辅以在指数时间假设(ETH)下与之匹配的下界:
**定理 1** 有标签可收缩性
- 存在运行时间为 $2^{O(\text{tw}^2)} \cdot |V(G)|^{O(1)}$ 的算法;但
- 不存在运行时间为 $2^{o(\text{tw}^2)} \cdot |V(G)|^{O(1)}$ 的算法,除非 ETH 不成立。
我们注意到,该下界在以路径宽为参数时同样成立,而路径宽是一个更大的参数。大多数已知的基于树分解进行动态规划的 FPT 算法的运行时间及匹配下界形式为 $2^{O(\text{tw})} \cdot n^{O(1)}$ [20, 第 7、13 章] 或 $2^{O(\text{tw} \log \text{tw})} \cdot n^{O(1)}$ [22], [44]。对于相对稀少的一组展现对树宽双指数依赖的问题,参见 [17], [31], [52] 及其引用文献。据我们所知,唯一具有路径宽的单指数但多项式依赖的问题仅在 [21], [48], [49] 中有提及。以顶点覆盖数为参数的类似结果可参见 [3], [6], [16], [32]。
Lafond 和 Marchand [42] 观察到退化度等较小的参数无法得到可处理的结果。具体而言,已知最大公共有标签收缩问题即使两个输入图都具有常数最大度数(从而常数退化度)时仍是 NP-难的,且有标签可收缩性对退化度有界的图是 NP-难的 [46, 定理 8]。我们通过在更严格的约束下证明难度来强化后者结果:
**定理 2** 即使 $G$ 和 $H$ 的最大度数都有界,有标签可收缩性仍然是 NP-难的。
这些结果表明,当仅以解的大小 $k$ 或退化度 $\delta(G)$ 作为参数时,不太可能达到可处理性。尽管如此,Lafond 和 Marchand [42] 证明该问题在组合参数 $(k + \delta(G))$ 下变得可处理,给出了一个运行时间为 $(\delta(G) + 2k)^k \cdot n^{O(1)}$ 的算法。他们提出了在该参数化下是否存在亚指数时间算法的问题,我们对此给出了否定回答。
对于紧密相关的公共收缩问题的难度归约也使用了集合分裂问题,等价于不全等 SAT 的正变体 [46]。对于以下条件性下界,我们改用 1-in-3-SAT,我们首先建立了所需的 ETH 下界,然后给出了到有标签可收缩性的线性规模归约。
**定理 3** 除非 ETH 不成立,否则即使 $G$ 和 $H$ 的退化度都有界,有标签可收缩性也不存在运行时间为 $2^{o(|V(G)| + |E(G)|)}$ 的算法。
该定理在 ETH 假设下排除了以 $(k + \delta(G))$ 为参数的亚指数时间算法的可能性。我们还提供了以下改进算法:
**定理 4** 有标签可收缩性可以在时间 $(\delta(H) + 1)^k \cdot |V(G)|^{O(1)}$ 内求解,其中 $k = |V(G) \setminus V(H)|$ 是所需的收缩次数,$\delta(H)$ 是 $H$ 的退化度。
该算法改进了 [42, 第 3.3 节] 中 $(\delta(H) + k)^k \cdot n^{O(1)}$ 的算法。
最后,作为我们的最后一个贡献,我们分析了有标签可收缩性的暴力算法并证明了其在 ETH 下的最优性。值得注意的是,我们的分析也适用于更一般的最大公共有标签收缩问题。
**定理 5** 有标签可收缩性
- 存在运行时间为 $|V(H)|^{O(|V(G)|)}$ 的算法;但
- 不存在运行时间为 $|V(H)|^{o(|V(G)|)}$ 的算法,除非 ETH 不成立。
**组织结构。** 我们采用图论和参数化复杂度中的标准符号,如第 2 节所述。第 3 节提出了基于树分解的动态规划算法并建立了与之匹配的下界。具体而言,我们提供了从亚三次分区顶点覆盖问题 [3] 的参数保持归约,证明了定理 1。第 4 节通过从正-不全等 SAT 的归约证明了定理 2,表明即使对于最大度数有界的图,问题也是 NP-难的。第 5 节专门讨论 ETH 下的条件性下界。利用从 1-in-3-SAT 的归约,我们证明了即使在两个输入图的退化度都有界时,该结果依然成立。我们还给出了一个针对组合参数 $(k + \delta(G))$ 的改进 FPT 算法。这些结果共同建立了定理 3 和定理 4。第 6 节分析了暴力算法并证明了其在 ETH 下的最优性,这是通过从交叉匹配问题 [29] 的归约实现的,并建立了定理 5。最后,第 7 节以开放问题和猜想作为结论。
## 各节片段
### 预备知识
对于正整数 $n$,我们记 $[n] = \{1, 2, \ldots, n\}$。设 $G$ 为一个图。我们用 $V(G)$ 和 $E(G)$ 分别表示 $G$ 的顶点集和边集。若 $(u, v) \in E(G)$,则称两个顶点 $u, v \in V(G)$ 相邻。对于顶点 $u \in V(G)$,用 $N_G(u)$ 表示 $u$ 的(开)邻域,即 $G$ 中所有与 $u$ 相邻的顶点的集合,并定义闭邻域为 $N_G[u] = N_G(u) \cup \{u\}$。当上下文清晰时我们省略下标。给定两个不相交的子集 $X, Y \subseteq V(G)$,我们说 $X$ 和 $Y$……
### 以树宽为参数
在本节中,我们给出定理 1 的证明,这里重新陈述如下。
**定理 1** 有标签可收缩性
- 存在运行时间为 $2^{O(\text{tw}^2)} \cdot |V(G)|^{O(1)}$ 的算法;但
- 不存在运行时间为 $2^{o(\text{tw}^2)} \cdot |V(G)|^{O(1)}$ 的算法,除非 ETH 不成立。
在第一小节中,我们通过呈现基于树分解的动态规划算法来描述算法性结果。在第二小节中,我们建立了与之匹配的条件性下界。
### 最大度数有界时的 NP-困难性
在本节中,我们通过建立有标签可收缩性问题的 NP-困难性来证明定理 2。为方便读者,我们重新陈述如下。
**定理 2** 即使 $G$ 和 $H$ 的最大度数都有界,有标签可收缩性仍然是 NP-难的。
我们呈现从正-不全等 (3,4)-SAT 到有标签可收缩性的多项式时间归约,即使在两个输入图 $G$ 和 $H$ 都具有常数最大度数的情况下。源问题的正式定义如下,且已知是 NP-完全的 [23]。
我们可以……
### 以解大小加退化度为参数
我们在以下两个小节中分别证明定理 3 和定理 4。
### 暴力算法及其最优性
我们现在证明定理 5,为方便读者重新陈述如下。
**定理 5** 有标签可收缩性
- 存在运行时间为 $|V(H)|^{O(|V(G)|)}$ 的算法;但
- 不存在运行时间为 $|V(H)|^{o(|V(G)|)}$ 的算法,除非 ETH 不成立。
### 结论
在本文中,我们推进了 Lafond 和 Marchand [42] 开创性工作基础上的有标签可收缩性的参数化复杂度研究。我们开发了一个构造性的动态规划算法,运行时间为 $2^{O(\text{tw}^2)} \cdot n^{O(1)}$,相较于先前已知的基于元定理且对树宽具有非初等依赖的方法有了显著改进。此外,我们辅以在指数时间假设下与之匹配的条件性下界。
---
**CRediT 作者贡献声明**
Yashaswini Mathur:写作 – 审阅与编辑,写作 – 原稿撰写,可视化,验证,调查,形式化分析,概念构思。
Prafullkumar Tale:写作 – 审阅与编辑,写作 – 原稿撰写,可视化,验证,监督,方法论,调查,形式化分析,概念构思。
Yashaswini Mathur | Prafullkumar Tale
生物通微信公众号
生物通新浪微博
今日动态 |
人才市场 |
新技术专栏 |
中国科学人 |
云展台 |
BioHot |
云讲堂直播 |
会展中心 |
特价专栏 |
技术快讯 |
免费试用
版权所有 生物通
Copyright© eBiotrade.com, All Rights Reserved
联系信箱:
粤ICP备09063491号