孪生宽度有界的图上高度难近似问题的近似算法

《Journal of Computer and System Sciences》:Approximating highly inapproximable problems on graphs of bounded twin-width

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

编辑推荐:

   摘要 对于任意 ε>0,我们针对附带 O(1)-序列的有界孪生宽度图,给出了最大独立集问题的多项式时间 n^ε-近似算法。该结果源自以下时间与近似的权衡:对于每个整数 q≥0,我们建立了一个 O(1)^{2^{q-1}}-近似算法,其运行时间为 exp(O_q(n^{2-q

  

摘要

对于任意 ε>0,我们针对附带 O(1)-序列的有界孪生宽度图,给出了最大独立集问题的多项式时间 n^ε-近似算法。该结果源自以下时间与近似的权衡:对于每个整数 q≥0,我们建立了一个 O(1)^{2^{q-1}}-近似算法,其运行时间为 exp(O_q(n^{2-q}))。基于同一框架,我们为最小着色和最大导出匹配问题获得了类似的近似算法。在一般图中,这些问题均为高度不可近似的:对于任意 ε>0,其中任何问题的多项式时间 n^{1-ε}-近似算法都将蕴含 P=NP。我们将最大独立集和最大导出匹配的算法推广为任意固定连通图 H 的独立(导出)打包问题。相比之下,我们证明在附带 O(1)-序列的有界孪生宽度图上,最小独立支配集问题极不可能达到类似的近似保证,而最长路径和最长导出路径问题也较为不可能。关于是否存在更好的近似算法,有(非常)微弱的证据表明,最大独立集问题所得到的 n^ε 近似因子可能已是最优的。本文是首篇对有界孪生宽度图中问题可近似性进行深入研究的论文。在此之前,该方向上仅有的结果是一个针对最小支配集问题的多项式时间 O(1)-近似算法。

引言

孪生宽度是由 Bonnet、Kim、Thomassé 和 Watrigant 引入的图参数。其定义涉及三重图和收缩序列的概念。三重图是一种具有两种边的图:黑边(普通边)和红边(错误边)。(顶点)收缩是指将两个(不一定相邻的)顶点 u 和 v 合并为一个顶点 w,使得当且仅当 uz 和 vz 之前均为黑边时,保留边 wz 为黑边。与 w 关联的其他边变为红边(若此前不是红边),三重图的其余部分保持不变。n 个顶点的图 G 的收缩序列是一系列三重图 G=G_n,…,G_1=K_1,其中 G_i 由 G_{i+1} 执行一次收缩得到。d-序列是指每个三重图中每个顶点的关联红边数至多为 d 的收缩序列。G 的孪生宽度,记为 tww(G),是使 G 存在 d-序列的最小整数 d。图 1 给出了一个具有 2-序列(即孪生宽度至多为 2)的图的例子。孪生宽度可自然地推广到有限字母表上的矩阵(具有无序或有序的行集和列集),并进一步推广到二元结构。

一种等价且更方便的视角是将 d-序列视为 V(G) 的划分序列 P_n:={{v}: v∈V(G)}, P_{n-1},…,P_1:={V(G)},使得对于每个整数 1≤i≤n-1,P_i 有 i 个部分,且由 P_{i+1} 中的两个部分合并为一个部分得到。此时,划分中某部分 P∈P_i 的红度是指 P_i 中其他部分 Q 的个数,使得 G 中 P 与 Q 之间至少有一条边且至少有一个非边。d-序列是指序列中任何划分中任何部分的红度都不超过 d 的序列,此时每个划分的最大红度至多为 d。类似地,我们得到 G 的孪生宽度为使得 G 存在(划分)d-序列的最小整数 d。商三重图 G/P_i 即为三重图 G_i,前提是(收缩)d-序列 G_n,…,G_1 与(划分)d-序列 P_n,…,P_1 相对应。

具有有界孪生宽度的二元结构类包括具有有界树宽的图类,更一般地,有界团宽类、恰当闭包类、具有有界大小反链的偏序集、排列图的严格子类,以及 n 个顶点图的 Ω(log n)-细分类,和一些(有界度)扩展器类。许多几何定义的图类也具有有界孪生宽度,例如地图图、有界度字符串图,具有有界队列数或有界栈数的类,不含 K_{t,t} 子图的线段图,不含大半图的 1.5D 地形可视图,以及不含大独立集的简单多边形可视图。

对于前面提到的每个类 C,可在多项式时间内计算 C 中成员的 O(1)-序列。对于包含解释为域上线性序的二元关系的二元结构类(称为有序二元结构),孪生宽度存在固定参数近似算法。具体而言,给定图 G 和整数 k,存在可计算函数 f 和 g,使得可在时间 g(k)n^{O(1)} 内输出 G 的 f(k)-序列,或正确报告 tww(G)>k。对于一般的(不一定有序的)二元结构类,特别是所有图的类,目前尚无此类近似算法。我们还观察到,判定一个图的孪生宽度是否至多为 4 是 NP 完全问题。

因此,我们将假设输入图附带一个 d-序列给出,并将 d 视为常数(或假设输入来自上述任一类)。迄今为止,设计有界孪生宽度图上的更快算法时所采用的正是这一设定。自孪生宽度被引入以来——实际上从 Guillemot 和 Marx 的开创性工作开始——就很清楚,在此不变量有界的结构中往往可以设计参数化算法。更具体地说,已证明在附带 d-序列的图 G 上,模型检查一阶公式 φ 是固定参数可解的——可在时间 f(d,φ)·n 内求解——例如 k-独立集或 k-支配集等特殊情形可接受单指数参数化算法,几乎线性于 n 的高效数据结构可支持常数时间的边查询,G 中的三角形可在时间 O(d2n + m) 内计数。

然而,到目前为止,具有有界孪生宽度与获得更好近似因子之间的联系仍然薄弱。唯一相关的结果涉及最小支配集问题,该问题在一般图中以因子 (1?o(1))ln n 近似已被证明不可近似(除非 P=NP),但在附带 O(1)-序列的有界孪生宽度图上却接受常数近似。我们通过设计针对附带 O(1)-序列的有界孪生宽度图上问题的近似算法来填补这一空白,特别是最大独立集、最大导出匹配和着色问题。在该特定场景中为最大独立集和着色问题获得更好的近似算法曾是一个公开问题。在我们描述结果并详细说明所开发的技术之前,让我们简要介绍这些问题在一般图中的著名不可近似性。

最大独立集和着色问题是 NP 难的,且高度不可近似:对于每个 ε>0,以任何比率 n^{1-ε} 近似这些问题都是 NP 难的。最大导出匹配问题亦然。此外,在 2^{O(n)} 的暴力算法基础上几乎没有改进空间:除非指数时间假设失败,否则没有算法可在时间 2^{o(n)} 内解决最大独立集(以及其他两个问题)。对于任何 r(可能是 n 的函数),最大独立集的加权变体(WMIS)可在时间 2^{O(n/r)} 内获得 r-近似。Bansal 等人基本上将后者的指数减去了一个 log_2 r 因子。已知多项式级别的削减不太可能。Chalermsook 等人证明,对于任意 ε>0 和足够大的 r(同样 r 可以是 n 的函数),最大独立集和最大导出匹配的 r-近似算法不可能在时间 2^{O(n^{1-ε}/r^{1+ε})} 内完成,除非指数时间假设失败。例如,投入时间 2^{O(n)},不可能期望显著优于 n-近似。

贡献与技术

我们的起点是:当附带 O(1)-序列时,最大独立集可在时间 2^{O(n)} 内获得常数近似的算法,根据 Chalermsook 等人的结果,这在一般图中极不可能成立。

定理 1 在附带 d-序列的 n 个顶点图上,最大独立集可在时间 2^{O_d(n)} 内获得 O_d(1)-近似。

我们的算法基于孪生宽度与所谓通用孪生宽度之间的函数等价关系。我们将正式定义留待第 2 节。对于我们的目的,只需知道以下该等价关系的一个有用推论:从 G 的 d'-序列出发,可在多项式时间内计算另一个宽度为 d:=f(d') 的 G 的划分序列 P_n,…,P_1,其中 f 是某个可计算函数,使得对于每个整数 1≤i≤n,P_i 的所有 i 个部分的大小至多为 d·n^i。即使 P_i 中的某些部分可能非常小,该划分是平衡的,即任何部分的大小不会超过完全平衡划分中部分大小的 d 倍。对我们而言重要的是当部分数量(?n?)和划分中最大部分的大小(至多 d·n/?n?≈d·n)较为平衡时的 P_{?n?}。

然后我们可以用 d+1 种颜色对红图(由 P_{?n?} 顶点集上的红边构成)进行正常着色。任何颜色类 X 是 P_{?n?} 部分的子集,其中任意两个部分之间要么全有边(黑边)要么完全无边(非边)。用图论术语来说,G 中由 X 的所有部分的所有顶点诱导的子图 G_X 具有简单的模分解:一个由至多 ?n? 个模块组成的划分,每个模块的大小至多为 d·n/?n?。因此,计算 G_X 的最大独立集的时间基本上在模块数与最大模块大小之间的最大值的指数级内,即在至多 d·n 时间内。由于某个颜色类 X* 包含超过最优解 1/(d+1) 的部分,当我们计算 G_{X*} 的最大独立集时,便得到了 d+1-近似。第 10 页的图 2 为我们迄今为止所描述内容提供了直观总结。

下一步是用在 O_d(n) 大小导出子图上的精确指数算法替换近似算法中的递归调用。沿此归纳过程在深度 q=2,3,4,… 处,近似比降为 (d+1)^3, (d+1)^7, (d+1)^15 等,但运行时间相应提升至 2^{O_d(n^{1/4})}, 2^{O_d(n^{1/8})}, 2^{O_d(n^{1/16})} 等。实际上,我们通过归纳证明了:

定理 2 在附带 d-序列的 n 个顶点图上,对于每个整数 q≥0,最大独立集存在一个 O_d(1)^{2^q?1}-近似算法,运行时间为 2^{O_{d,q}(n^{2-q})}。

直接从定理 2 可推导出近似比为 n^ε 的多项式时间算法,只需选择适当的 q 值即可。具体来说,为了给读者一些初步直觉,q 值渐近地确定为 q=log_2(ε log n)+O_d(1)。

推论 3 对于每个 ε>0,在附带 d-序列的 n 个顶点图上,最大独立集可以多项式时间 O_{d,ε}(1)·log_{O_d(1)}(n)·n^{O(1)} 获得 n^ε-近似。注意多项式因子的指数是绝对常数(不依赖于 d 或 ε)。

随后我们将框架应用于着色和最大导出匹配。

定理 4 对于每个 ε>0,在附带 O(1)-序列的有界孪生宽度 n 个顶点图上,着色和最大导出匹配存在多项式时间 n^ε-近似算法。

对于着色问题,主要的额外困难在于不能仅通过对模块和商图着色来在模分解上满意地解决或近似该问题。需要处理一个称为集合着色的更一般问题。幸运的是,这一推广正是我们在寻找的不动点:在我们的框架中,近似集合着色仅通过递归调用(调用自身)即可完成。

对于最大导出匹配,我们面临一种新的障碍。在红图 G/P_{?n?} 的所选 d+1 着色中,可能没有任何颜色类 X 包含令人满意的解。例如,可能任何这样的颜色类 X 在 G 中诱导的图都是无边的,而非常大的导出匹配其端点存在于两个不同的颜色类中。因此,我们还需要在 G/P_{?n?} 的黑边中以及红边中查找大的导出匹配。这导致了一种更复杂的策略,交织着有界度图的着色(特别是红图及其线图平方的着色)以及对 G 的导出子图和 G/P_{?n?} 的全图(即由红边和黑边共同构成的图)的特殊导出子图的递归调用。

尽管这并不是必需的,但可以观察到,后者的图也是G本身的诱导子图。随后,我们探索了结果和框架在可处理问题方面的局限性。我们给出了关于MIS(最大独立集)和Max Induced Matching(最大诱导匹配)近似算法的以下技术性推广。

**定理5** 对于任意连通图H和ε>0,Mutually Induced H-packing(相互诱导H-打包)在具有O(1)-序列的有界孪生宽度n顶点图上,存在多项式时间的n^ε-近似算法。

在该问题中,我们寻找一个最大的诱导子图,使其由H的若干不相交副本的并组成。前述所有技术问题在此都综合在一起了。我们尝试将所有H的顶点分批到G/P?n?中至多|V(H)|个部分的所有可能性,这基于这些部分所定义的三色图。例如,当H=K?(一条边),即Max Induced Matching的情形时,三种可能的三色图为:1-顶点三色图、两个顶点之间用红边相连、以及两个顶点之间用黑边相连。在一般情形下,找到问题的推广相当精细。我们必须在V(G)和V(H)上保留一些划分,以强制G中的H的副本遵循算法在递归树更高层次所确定的模式,并且在G的|V(H)|元组上设定一个权重函数,不忘记这些顶点中可容纳多少个相互诱导的H副本。另一个新颖之处在于,某些递归调用是针对G/P?n?的全图的诱导子图,而这些子图并非G的诱导子图。幸运的是,这些图保持了相同的多样化孪生宽度界限,因此我们的框架允许这样做。

对于图族H,定义Mutually Induced H-packing为相同的问题,只是诱导子图的连通分量应都在H中,当H为有限连通图集合时,我们得到相似的近似因子。(注意Mutually Induced H-packing有时也被称为Independent Induced H-Packing。)特别地,我们可以类似地近似Independent H-Packing,这是同样的问题,但H的副本不需要是诱导的。(我们的近似算法可以扩展到不需要独立性的其他H-打包变体,但这些问题在一般图中可以被O(1)近似。)

我们也能处理H为无限集合的某些情况。例如,通过略微调整MIS的情形,当H是所有团(cliques)的集合时,我们可以得到n^ε-近似。我们展示了一个更复杂的例子,也可表述为:当H是所有树的集合或所有星形图的集合时。

**定理6** 对于任意ε>0,在具有O(1)-序列的有界孪生宽度n顶点图上,寻找拥有最多边的诱导(星形)森林存在多项式时间的n^ε-近似算法。

正如我们已经提到的,我们的框架专门适用于在一般图中非常难近似的,至少对于每个ε>0而言n^ε-近似算法未知的的问题。在孪生宽度有界的图中,是否存在自然的问题无法被更好地近似?我们通过Min Independent Dominating Set(最小独立支配集)的例子肯定地回答了这个问题。

**定理7** 对于任意ε>0,除非P=NP,否则Min Independent Dominating Set在具有O(1)-序列的n顶点图上不存在n^(1?ε)-近似算法。

归约与一般图中的相同[22],但源自3-SAT的一个平面变体。所获得的实例不是平面图,但可以收缩为平面三色图,因此总体上具有有界孪生宽度。

最后,Longest Path(最长路径)和Longest Induced Path(最长诱导路径)的情形很有趣。前者的最佳近似因子[18]比n^0.99更差,而后者的不可近似性与MIS相同[31]。然而,对于Longest Path,n^ε-近似算法(对于每个ε>0)并未被排除。我们证明,有界孪生宽度的性质对这两个问题不太可能有帮助,因为这将为一般图中的Longest Path带来更好的近似算法。这主要是因为将任意n顶点图的每条边细分至少2log n次后,得到的图的孪生宽度至多为4[3]。

**定理8** 对于任意r=ω(1),在具有O(1)-序列的图上的Longest Induced Path或Longest Path的r-近似,将意味着一般图中Longest Path的(1+o(1))r-近似。

反过来,这可以用来展示一个族H,它是诱导子图关系下的无限反链,使得在孪生宽度有界的图中Mutually Induced H-packing难以n^ε-近似。该族H简单地是所有两端以三角形终止的路径的集合。

**定理9** 存在无限连通图族H,使得如果对于每个ε>0,在具有O(1)-序列的n顶点图上Mutually Induced H-packing存在n^ε-近似算法,那么一般图中的Longest Path也存在。

表1总结了我们的结果并暗示了未来工作。

对于主要的极高不可近似图问题,我们在具有O(1)-序列的孪生宽度有界的图中,要么获得了n^ε-近似算法,要么找到了条件性阻碍(即不存在这样的近似算法的证明)。在前者情况下,我们能否进一步改进近似因子?以下定理利用了Feige等人[17]的自我改进归约,该归约保持了孪生宽度界限。该归约的实质是从图G转到其词典积G[G],其中G的每个顶点被替换为诱导一个G的副本的模(并迭代此技巧)。

**定理10**[7] 设r:N→R为任意非递减函数,使得对于每个ε>0,有r(n)=o(n^ε)。如果Max Independent Set在具有O(1)-序列的孪生宽度有界的n顶点图上存在r(n)-近似算法,则它进一步存在r(n)^ε-近似。

据我们所知,自我改进技巧的应用总是用来加强下界,而从未用于轻易获得更好的近似因子。因此,我们可以将定理10视为我们的近似比率可能是最优的弱证据。尽管如此,即使是多项式时间近似方案(PTAS),对于MIS(以及Max Induced Matching、Min Dominating Set等)也未被排除,我们希望能看到更好的近似算法。对于Coloring(着色),正如先前所观察到的[7],由于判定平面图是3-可染还是4-染色的NP困难性,PTAS被排除了,因为平面图的孪生宽度至多为8,且可以在线性时间内找到一个8-序列[24]。

**章节片段**

**预备知识**

对于两个整数i和j,我们用[i,j]表示大于等于i且小于等于j的整数集合。对于每个整数i,[i]是[1,i]的简写。

**最大独立集的近似算法**

我们自然地从Max Independent Set开始我们的研究,这是一个非常难近似[23][34]的核心问题,同时也是我们方法的教科书式示例。

**寻找合适的推广:Coloring的情形**

在本节中,我们处理Coloring问题。与WMIS不同,我们不能仅仅依赖递归调用Coloring算法于更小的图。需要找到正确的推问题,使得归纳调用能够顺利进行,而这恰好是Set Coloring。

在Set Coloring问题中,输入是一对(G,b),其中G是一个图,b是一个为G的每个顶点分配一个正整数的函数。目标是找到对于每个v∈V(G),一个至少包含b(v)种颜色的集合S_v,颜色……

**基于边的问题:Max Induced Matching的情形**

到目前为止,我们只考虑了在V(G)的某个小宽度划分P的每一部分P_i中近似解,以及在(G/P,E(G/P))的某些选定诱导子图中的近似解足以构造G的近似解的问题。现在我们处理需要优化边数的问题。现在所有竞争性解都可以完全位于由黑边或红边相连的部分对P_i,P_j之间……

**Mutually Induced H-packing**

在本节中,我们提出了Max Independent Set和Max Induced Matching的近似算法的深远推广。对于任意固定图H,设Mutually Induced H-packing为在输入图G中寻找最大的相互诱导H副本集合的问题,即寻找最大的集合S,使得G[S]是(H的副本的)不相交并。对于任何连通图H,我们都获得了类似的近似保证。注意Max……

**局限性**

现在我们讨论我们框架的局限性。我们给出一些不太可能在孪生宽度有界的图中具有n^ε-近似算法的问题的例子。第一个这样的问题是Min Independent Dominating Set,在其中寻找一个既是最小独立集又是最小支配集的最小基数集合。在一般n顶点图中,除非P=NP,否则该问题不能在多项式时间内n^(1?ε)-近似[22],也不能在2^(o(n/r))时间内r-近似,对于任何r=r(n),除非C……

*作者贡献声明*

Pierre Bergé:写作 – 审阅与编辑、写作 – 原始草稿、调查、形式分析、概念化。édouard Bonnet:写作 – 审阅与编辑、写作 – 原始草稿、调查、形式分析、概念化。Hugues Déprés:写作 – 审阅与编辑、写作 – 原始草稿、调查、形式分析、概念化。Rémi Watrigant:写作 – 审阅与编辑、写作 – 原始草稿、调查、形式分析、概念化。

Pierre Bergé | édouard Bonnet | Hugues Déprés | Rémi Watrigant
相关新闻
生物通微信公众号
微信
新浪微博
  • 搜索
  • 国际
  • 国内
  • 人物
  • 产业
  • 热点
  • 科普

热点排行

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

    版权所有 生物通

    Copyright© eBiotrade.com, All Rights Reserved

    联系信箱:

    粤ICP备09063491号