论带有长度约束的顶点不相交A-路径打包问题的参数化可处理性

《Journal of Computer and System Sciences》:On the Parameterized Tractability of Packing Vertex-Disjoint A-Paths with Length Constraints

【字体: 大 中 小 】 时间:2026年10月02日 来源:Journal of Computer and System Sciences 1.4

编辑推荐:

   摘要 给定一个无向图G和一个集合A?V(G),一条A-路径是G中一条起点和终点分别为A中两个不同顶点、中间顶点均在V(G)?A中的路径。若该路径的长度恰好为?,则称其为(A,?)-路径。在(A,?)-路径 packing问题(ALPP)中,我们寻求判断G中是否存在k条顶点不相

  

摘要 给定一个无向图G和一个集合A?V(G),一条A-路径是G中一条起点和终点分别为A中两个不同顶点、中间顶点均在V(G)?A中的路径。若该路径的长度恰好为?,则称其为(A,?)-路径。在(A,?)-路径 packing问题(ALPP)中,我们寻求判断G中是否存在k条顶点不相交的(A,?)-路径。已知当以k+?为参数时,利用颜色编码技术该问题是固定参数可解(FPT)的;但当仅以k(哈密顿路径问题)或仅以?(P3-划分问题)为参数时,该问题是Para-NP难的。因此,从结构参数角度研究该问题是一个合理的方向。Belmonte等人[Algorithmica 2022]开启了这一方向的研究,并证明了ALPP以pw+|A|为参数时是W[1]-难的,其中pw为输入图的路径宽度。在本文中,我们强化了他们的结果,证明了即使以更复杂的参数(|A|+dtp)为参数,ALPP也不太可能是固定参数可解的,其中dtp表示输入图到路径图的距离。在此基础上,我们考虑了参数cvd+|A|和cvd+?,并给出了关于这些参数的FPT算法。最后,当以输入图的顶点覆盖数vc为参数时,我们为(A,?)-路径 packing问题给出了一个O(vc2)的顶点核。

引言 不相交路径问题构成了算法图论中的一个基本问题类。这些已被广泛研究的问题旨在找到满足特定附加约束的最大的顶点不相交(或边不相交)路径集合。值得注意的是,在不存在附加约束的情况下,该问题退化为经典的完美匹配问题。不相交路径问题中被研究最广泛的变体之一是s-t不相交路径问题,给定一个图G和两个顶点s、t,目标是找到s与t之间数量最多的内部顶点不相交路径。该问题可以通过利用Menger定理归约为最大流问题,在多项式时间内求解。

不相交路径问题的另一个经典版本是Mader的S-路径问题。对于图G和V(G)的一族两两不相交的子集S,S-路径是连接S中不同成员的两个顶点之间的路径。给定G和S,Mader的S-路径问题的目标是找到数量最多的顶点不相交S-路径。Chudnovsky、Cunningham和Geelen[10]、[22]、[25]已证明该问题可在多项式时间内求解。与Mader的S-路径问题密切相关且广为人知的一个变体是A-路径 packing问题[6]、[8]、[11]、[19]、[24]。给定图G和顶点子集A,A-路径是G中一条起点和终点分别为A中两个不同顶点、内部顶点来自V(G)?A的路径。A-路径 packing问题的目标是找到G中数量最多的顶点不相交A-路径。A-路径 packing问题可建模为S-路径问题,其中对每个顶点v∈A,我们在S中创建集合{v}。因此,A-路径 packing问题变为多项式时间可解的。

最近,Golovach和Thilikos[18]探索了经典s-t路径问题的一个有趣变体,即有界s-t路径问题,该问题通过引入对路径长度的附加约束。在此变体中,给定图G、两个不同顶点s和t以及一个整数?,目标是找到s与t之间长度至多为?的数量最多的顶点不相交路径。令人意外的是,加上这一约束后,问题变得困难,这与经典的s-t路径问题形成对比。在类似的研究方向上,Belmonte等人[6]考虑了A-路径 packing问题的以下变体。

这一版本的A-路径 packing问题也被证明是不可解的[6]。在参数化框架下考虑该问题,ALPP最自然的两个参数分别是解的大小k和长度约束?。当以组合参数k+?为参数时,该问题通过颜色编码(一种在[1]、[2]、[3]中使用的方法)可轻松获得FPT算法;但当仅以单个参数k或?为参数时,由于分别可以从哈密顿路径问题和P3- packing问题进行归约,该问题变为Para-NP难的。

虽然似乎参数化框架内的探索可能性已被穷尽,但另一组被称为结构参数的参数出现,允许进一步的调查。Belmonte等人[6]通过考虑集合A的大小(|A|)作为参数开启了这一研究方向。他们证明了该问题以组合参数(图的路径宽度和|A|)即pw+|A|为参数时是W[1]-难的。这一W[1]-难的结果同样可转化为以tw+|A|(即输入图的树宽与|A|的组合参数)为参数时的W[1]-难结果。

参数tw+|A|的不可解性结果否定了为许多著名结构参数获得FPT算法的可能性。尽管如此,结构参数化的目标之一在于界定问题可解性的边界,即确定使问题变为FPT的最小参数,或使问题变为W-难的最大参数。因此,一个自然的方向是研究ALPP关于大于或与tw+|A|不可比的参数的情况。

我们的贡献:作为第一个结果,我们通过证明一个远大于pw+|A|的参数dtp+|A|的难度来改进Belmonte等人[6]的难度结果。这里dtp表示输入图到路径图的距离(所有参数的正式定义见第2节)。具体而言,我们的算法下界结果是一个W-难度结果,在rETH(猜想2.4)下证明了更强的结论,如下所述。

定理1.1 除非猜想2.4不成立,否则不存在随机算法能在f(dtp+|A|)·n^{o(dtp+|A|)}时间内运行并以至少2/3的概率正确判定(A,?)-路径 packing问题(其中dtp为到路径图的距离)。

我们通过从众所周知的W[1]-难问题构造一个随机归约来建立难度,从而在随机化指数时间假设(rETH)下确立了(A,?)-路径 packing问题的难度。我们在证明中使用的随机归约技术具有高度适应性,可用于证明各种类似问题为难的。我们使用以下引理来证明难度结果,该引理本身也可能具有独立的研究价值。

引理1.2 分离引理 设(X, F)为一个集系统,其中F是X的子集族。对于权重赋值w: X→[M]的任意分配,令w(S) = Σ_{x∈S} w(x)表示子集S?X的权重。对于将X中各元素的权重独立且均匀地从[M]中随机分配的任意方案,以至少1-(|F|2/M)的概率,每个集合S∈F具有唯一的权重。

除细化难度边界外,我们还考虑了关于参数cvd(聚类顶点删除数)与|A|和?的组合问题。cvd与tw和pw的不可比性使其成为一个值得探索的有趣参数。我们证明了ALPP关于参数cvd+|A|和cvd+?均是固定参数可解的。具体地,我们证明了以下两个固定参数可解性结果。

定理1.3 (A,?)-路径 packing以cvd+|A|为参数时是FPT的。

定理1.4 (A,?)-路径 packing以cvd+?为参数时是FPT的。

最后,对于(A,?)-路径 packing问题,利用新的q-扩张引理和精心设计的特定方法,我们针对更大的参数——顶点覆盖数vc(vc大于cvd、pw和tw中的每一个)设计了一个二次顶点核。具体地,我们证明了以下结果。

定理1.5 (A,?)-路径 packing以vc(顶点覆盖数)为参数时,存在一个包含O(vc2)个顶点的核。

我们论文的编排如下。在第2节中,我们介绍图论和参数化复杂性的基本定义。接着,在第3节中我们证明主要结果,即定理1.1。随后,我们在第4节和第5节中分别证明定理1.3和定理1.4。最后,在第6节中我们证明定理1.5。

各节摘要

预备知识与符号 集合、数与图论:我们用N表示所有自然数的集合,对每个r∈N用[r]表示集合{1,…,r}。给定有限集S和r∈N,我们用(S^r)和(S^{≤r})分别表示S的恰好包含r个元素的子集集合和至多包含r个元素的子集集合。我们采用Diestel[14]著作中的标准图论记号。对于图G,若对任意顶点对u,v∈W都有uv?E(G),则顶点集W?V(G)称为独立的。等价地,一个集合W?V(G)是

基于rETH、以dtp+|A|为参数的算法下界 本节确立了在标准复杂性理论假设下,ALPP以组合参数(dtp+|A|)为参数时不太可能是固定参数可解的。我们首先介绍一些关键的思路,这些思路将对后续的难度归约起到关键作用。

以cvd+|A|为参数的FPT算法 本节为(A,?)-路径 packing问题设计了一个FPT算法,参数由聚类顶点删除集的大小和|A|的组合确定。我们的算法假设输入中包含一个最小规模的集合M,满足条件A?M且G?M构成一个聚类图。这一假设是合理的,因为可以在时间1.9102k·n^{O(1)}内高效找到G?A的最小规模聚类顶点删除集[7]。

以cvd+?为参数的FPT算法 本节为ALPP设计了一个FPT算法,参数为组合参数cvd+?。设输入图为G,含有两个子集A, M?V(G),使得G?M为聚类图,|A|=a,|M|=m=cvd(G)。所考虑的参数为m+?。我们将G?M中的团集合记为Q,将团中的顶点集合记为VQ=∪_{Q∈Q} V(Q)。设I=(G,M,A,k,?)为ALPP的一个YES实例,P为I的任意一个解。我们将P中包含M中至少一个顶点的路径集合记为

以顶点覆盖数为参数的多项式核 本节为(A,?)-路径 packing问题设计了一个关于最小顶点覆盖大小的二次顶点核。给定输入图G,我们调用一个2-近似算法来计算顶点覆盖M,使得|M|≤2vc(G)。输入实例包含一个无向图G=(V,E)、两个集合A,M?V(G),其中M是一个顶点覆盖,|M|≤2vc(G),以及整数k和?。为便于记号,我们假设|M|=s。核化算法如下。设I=V(G?M),A_I=I∩

结论与未来工作 我们的结果通过考察多个结构参数下(A,?)-路径 packing(ALPP)的参数化复杂性状态,扩展了Belmonte等人[6]的工作。已知Belmonte等人[6]证明了ALPP以pw+|A|为参数时是W[1]-完全的。我们证明了关于一个远大于该参数的dtp(G)+|A|的不可解性结果。此外,ALPP以团宽与?的组合参数为参数时的参数化复杂性在Belmonte等人[6]中曾是一个开放问题。而这一问题

CRediT作者贡献声明 Susobhan Bandopadhyay:撰写——审稿与编辑,撰写——原始草稿,形式化分析,概念化。Aritra Banik:撰写——审稿与编辑,撰写——原始草稿,形式化分析,概念化。Diptapriyo Majumdar:撰写——审稿与编辑,撰写——原始草稿,形式化分析,概念化。Abhishek Sahu:撰写——审稿与编辑,撰写——原始草稿,形式化分析,概念化。

致谢 我们向Karthik C. S.教授和Saket Saurabh教授表示诚挚的谢意,感谢他们宝贵的建议和富有启发性的讨论。

Susobhan Bandopadhyay | Aritra Banik | Diptapriyo Majumdar | Abhishek Sahu
相关新闻
生物通微信公众号
微信
新浪微博

热点排行

    今日动态 | 人才市场 | 新技术专栏 | 中国科学人 | 云展台 | BioHot | 云讲堂直播 | 会展中心 | 特价专栏 | 技术快讯 | 免费试用

    版权所有 生物通

    Copyright© eBiotrade.com, All Rights Reserved

    联系信箱:

    粤ICP备09063491号