反馈集问题（feedback set problem）是计算机科学研究中最为广泛和深入的问题之一^[1]. 反馈集问题是求解图中的一个最小顶点集或边集，使得移除该集合后，图中不再存在环（cycle）. 早在20世纪中叶，反馈集问题就被引入用于解决时序逻辑电路（sequential logic circuit）的设计问题^[2]. 随后，它在竞赛排名^[3-4]、大规模集成电路设计^[5]、编码设计^[6-7]、软件验证^[8]等多个领域得到了应用. 20世纪末，反馈集问题的一般化形式——子集反馈集问题（subset feedback set problem）被提出. 该问题关注图中给定的一些“关键”元素，研究如何找到一个最小顶点或边集，使得移除该集合后，图中不再存在经过任何“关键”元素的环. 子集反馈集问题更具普适的实用性，可以根据不同场景定义不同的“关键”元素. 进入21世纪以来，社交网络和人工智能得到快速发展和普及^[9-10]，反馈集问题和子集反馈集问题引起了更多的研究兴趣也带来了更多应用价值.

1957年，麻省理工学院电子学研究实验室的一份技术报告^[2]指出，时序逻辑电路的设计需要在每一个逻辑信号环路上放置时钟脉冲门（clocked gate）、放大器（amplifier）等反馈元件，以确保电路的正常运作. 因此，一个电路所对应的有向图的最小反馈集大小表征了电路所需反馈元件的数量.

在软件工程领域，错误检测和调试是软件开发和维护的重要环节^[11]. 通过建立程序的依赖关系图并求解其反馈集，可以有效识别导致程序出错的或崩溃的关键路径和代码模块^[8]. 常见的应用之一是利用最小反馈集来解决操作系统死锁（deadlock）问题.

在社交网络中，节点表示个体，边表示个体间的关系. 反馈集和子集反馈集都可以用于识别社交网络中有影响力的用户、信息传播的重要节点等，这有助于预测可能形成的信息传播路径. 此外，有向反馈边集对于round-robin制竞赛的排名^[3-4]和选举排名^[12]等机制设计模型而言，也是一个十分有力的研究工具.

人工智能领域的许多问题可以建模为约束满足性问题（constraint satisfaction problem，CSP）并进行求解. 将约束满足性问题中的每一个变量表示为无向图的一个顶点，若2个变量之间存在约束关系，则连接1条边. 通过计算此无向图上的最小反馈点集，可优先对反馈点集上的变量进行赋值，便可高效地求解余下变量的最优赋值^[13]. 此外，贝叶斯推理（Bayesian inference）中的回路割问题（loop cutset problem）也可以借助有向图上的反馈集问题进行计算^[14].

在理论计算机领域，许多著名的问题与反馈集问题的计算复杂性密切相关. 例如，当最小反馈点集大小有界时，图同构问题可高效求解^[15]. 因此，这类问题都可预先计算最小反馈集进而能较快地完成求解.

反馈集和子集反馈集问题在各个领域中持续发掘新的应用价值，它们在复杂度理论和算法设计方面的研究也愈发深入，特别是在各类特殊图上的复杂性，其分类结果也趋于明确.

本文将对反馈集和子集反馈集2个问题从算法和计算复杂性的角度进行总结和探讨. 全文将包含2部分内容. 第1部分详尽地介绍了反馈集和子集反馈集问题各种不同形式的版本及其在一般图上的计算复杂性，然后梳理了各种不同版本之间的归约关系. 值得一提的是，本文对一些文献中未给出完整证明的命题以及一些尚未明确的归约关系进行了详细的补充和证明. 第2部分则进一步介绍了反馈集和子集反馈集问题在各种重要子图类上的精细计算复杂性，此类工作在以往的综述论文中涉及较少.

1.   问题定义与描述

对于一个图$G=(V,E)$，其中$V$表示点集，大小为$\left|V\right|=n$；$E$表示边集，大小为$\left|E\right|=m$. 图$G$上的反馈点集$S\subseteq V$（或反馈边集$S\subseteq E$）是指$G$中的一个点子集（或边子集），在删除$S$以后，剩余的图中没有环. 反馈集问题则是要求计算一个不超过给定大小的反馈集. 根据输入图是有向或是无向、反馈集是边集或是点集，可定义4类不同版本的问题：

1）（无向）反馈点集问题（feedback vertex set problem，FVS）；

2）（无向）反馈边集问题（feedback edge set problem，FES）；

3）有向反馈点集问题（directed feedback vertex set problem，DFVS）；

4）有向反馈边集问题（directed feedback arc set problem，DFAS）.

对4个问题的归类如表1所示.

表  1  反馈集问题类别

Table  1.  Variants of Feedback Set Problems

图类型	反馈集	问题简称
无向图	点集	FVS
无向图	边集	FES
有向图	点集	DFVS
有向图	边集	DFAS

下载: 导出CSV 

| 显示表格

接下来介绍一类更一般化的问题，称作子集反馈集问题. 在这类问题的输入中，除了图$G=(V,E)$外，还包括一个点子集$T\subseteq V$（或边子集$T\subseteq E$），称作关键集（terminal set）. 子集反馈集问题则是要求在删除不超过给定大小的点集或边集后，使得剩下的图中没有环包含关键集中的元素.

特别地，当$T$为图中所有顶点或边时，子集反馈集问题退化为经典的反馈集问题. 根据输入是有向或是无向、反馈集是边集或是点集以及关键集是边集或是点集. 可定义8类不同版本的问题：

1）（点）子集反馈点集问题（subset feedback vertex set problem，SFVS）；

2）（点）子集反馈边集问题（subset feedback edge set problem，SFES）；

3）边子集反馈点集问题（edge subset feedback vertex set problem，ESFVS）；

4）边子集反馈边集问题（edge subset feedback edge set problem，ESFES）；

5）有向（点）子集反馈点集问题（directed subset feedback vertex set problem，DSFVS）；

6）有向（点）子集反馈边集问题（directed subset feedback arc set problem，DSFAS）；

7）有向边子集反馈点集问题（directed arc subset feedback vertex set problem，DASFVS）；

8）有向边子集反馈边集问题（directed arc subset feedback arc set problem，DASFAS）.

此外，在一些实际场景中，关键集中的元素不允许被删除，换言之，反馈集中不允许包含关键集中的元素，这类问题被称为限制版（restricted version）. 当关键集与反馈集同为点集或边集时，均存在限制版本，分别记作R-SFVS（或R-DSFVS）以及R-ESFES（或R-DASFAS）. 对于没有这种限制要求的原问题，也称之为非限制版本（unrestricted version）. 综上，子集反馈集问题共分为12类，其中有向图和无向图上各6类. 对12类问题的归类如表2所示.

表  2  子集反馈集问题类别

Table  2.  Variants of Subset Feedback Set Problems

图类型	关键集	反馈集	限制与否	问题简称
无向图	点集	点集	非限制版	SFVS
	点集	点集	限制版	R-SFVS
	点集	边集	非限制版	SFES
	点集	边集	限制版
	边集	点集	非限制版	ESFVS
	边集	点集	限制版
	边集	边集	非限制版	ESFES
	边集	边集	限制版	R-ESFES
有向图	点集	点集	非限制版	DSFVS
	点集	点集	限制版	R-DSFVS
	点集	边集	非限制版	DSFAS
	点集	边集	限制版
	边集	点集	非限制版	DASFVS
	边集	点集	限制版
	边集	边集	非限制版	DASFAS
	边集	边集	限制版	R-DASFAS

下载: 导出CSV 

| 显示表格

2.   反馈集问题与子集反馈集问题的计算复杂性和归约关系

在计算理论中，将一个问题A归约（reduce）成问题B是指一个算法，该算法将问题A的任意一个输入实例（instance）转换成等价的一个问题B的实例. 若此算法可在多项式时间内完成，则称其为多项式时间归约（polynomial-time reduction）. 如果问题A可以归约到问题B，则可通过调用问题B的算法来求解问题A. 此外，若归约算法可使得2个问题中对应的某个参数的值不变，则称此归约保持了该参数不变.

虽然存在4类不同版本的反馈集问题以及多达12类不同版本的子集反馈集问题，但是反馈集问题与子集反馈集问题以及子集反馈集各类问题间存在非常紧密的归约关系. 本节将讨论反馈集以及子集反馈集问题之间的归约关系. 大部分归约关系在相关研究中已直接给出或可作为推论间接得出；而存在少量归约关系未在文献中明确记载. 本文将补充具体的归约算法和证明，以完整地给出各版本问题之间的归约关系. 凭借各版本之间的归约关系，相关的算法研究则通常聚焦于具有代表性的问题上. 通过研究代表性问题，其求解算法就能够很好地适用于其他多个不同版本的问题.

2.1   反馈集问题和子集反馈集问题间的基本归约关系

相较于反馈集问题，子集反馈集问题存在一个额外的输入，即关键集$T$. 在本节中，总是令$l$表示关键集T的大小. 当$T$取为图的全体点集或边集时，子集反馈集问题退化为反馈集问题. 因此，反馈点（边）集问题可以在多项式时间内归约到子集反馈点（边）集问题，且同时保持解集大小$l$不变.

另外，子集反馈集问题和边子集反馈集问题总可以相互归约，并且保持解集大小不变. 具体地，一方面，将子集反馈集问题实例中与关键点相邻接的边定义为关键边集，便将子集反馈集问题多项式时间归约到了边子集反馈集问题上；另一方面，将边子集反馈集问题中的每一个关键边替换为一个2度关键点，连接原边的2个端点，便将边子集反馈集问题多项式时间归约到了子集反馈集问题上.

2.2   无向图上的反馈集与子集反馈集问题

无向图上的反馈边集问题（FES）也是生成树问题（spanning tree problem）（仅表述方式不同）. 因此，FES可以在线性时间内求解. 相比之下，无向图上的反馈点集问题（FVS）则是NP难的，其归约来自康奈尔大学的算法研讨会^[16]上的一项成果.

无向图上的各版本子集反馈集问题均由Even等人^[17-18]于2000年前后提出. 3种子集反馈点集问题SFVS，ESFVS，R-SFVS的NP难性均可直接从FVS用类似的归约算法得到；而对于3种反馈边集问题，除限制版本R-ESFES为NP难外，其余2个非限制版本SFES和ESFES均能够在多项式时间求解^[19]. 具体地，Xiao等人^[19]证明了SFES可以在线性时间内求解，首先通过处理远离关键点的边，得到一个关键点“稠密”的无向图，然后通过研究该无向图的生成树的性质来设计线性时间的算法以求解SFES. 此外，随后进一步扩展该算法实现了对ESFES的求解，并且证明了ESFES仍然可以在线性时间内求解.

图1展示了无向图上2个反馈集问题和6个子集反馈集问题的归约关系. 利用ESFVS归约到SFVS的思想，可以将ESFVS归约到R-SFVS，并且保持解集大小k和关键集大小l不变. 具体构造方式为：将每一条边替换为1个限制点，此点为1个2度点，连接原边的2个端点. 该归约的正确性基于一个简单的事实：将一个解中的某个2度点替换为其邻居后，得到的集合仍然是一个解. 此外，使用常见的组件（gadget）替换技巧，将R-SFVS实例中的每一个关键点均替换为团（clique），即完全子图，能够得到R-SFVS到ESFVS的多项式时间归约. 由于此归约的具体构造未出现在文献中，本文在定理1中完整地给出了归约的构造方式.

图  1  无向图上反馈集和子集反馈集问题的归约关系

Figure  1.  Reductions among feedback set and subset feedback set problems in undirected graphs

下载: 全尺寸图片 幻灯片

定理1. R-SFVS可以在多项式时间归约到ESFVS并保持解集大小不变.

证明. 设R-SFVS的实例为$I=(G=\left(V,E\right),T,k)$，$I$为真当且仅当$G$中存在大小不超过$k$的解. 首先，不妨设$T$在$G$中为一个独立集. 这是因为如果存在2个关键点形成的1条边${t}_{1}{t}_{2}$，由于解集不允许包含关键点，因此将${t}_{1}{t}_{2}$合并成1个点（该点连接所有${t}_{1}$和${t}_{2}$的邻居）得到的实例与原实例等价. 对于每一个关键点${t}_{i}\in T$（$1\le i\le l$），设其度数为${d}_{i}$，${t}_{i}$的邻居表示为${u}_{i,1},{u}_{i,2},… , {u}_{i,{d}_{i}}\in V\backslash T$.

现构造ESFVS的实例$I'=({G}'=\left({V}',{E}'\right),{T}',{k}'=k)$，$I'$为真当且仅当$G'$中存在大小不超过${k}'=k$的解. 将每一个关键点${t}_{i}\in T$替换为一个大小为${d}_{i}$的团，其顶点集为$\{{x}_{i,1},{x}_{i,2},… ,{x}_{i,{d}_{i}}\}$. 经此替换操作，便得到了图${G}'=\left({V}',{E}'\right)$，其中顶点集${V}'=\left\{{v}':v\in V\backslash T\right\}\cup \{{x}_{i,j}:{t}_{i}\in T,1\le i\le l,1\le j\le {d}_{i}\}$，而边集$E'$的构造分为2种情况：

1）若原图$G$中2个非关键点$v$和$w$相连，则$G'$中${v}'$和${w}'$相连；

2）若原图$G$中的关键点${t}_{i}$和非关键点${u}_{i,j}$相连，则$G'$中${u}_{i,j}'$和替换${t}_{i}$的团中的${x}_{i,j}$相连.

所以边集可表示为${E}'=\left\{{v}'{w}':v,w\in V\backslash T,vw\in E\right\}\cup \{{x}_{i,j}{u}_{i,j}':1\le i\le l,1\le j\le {d}_{i}\}$. 令$G'$中关键边为顶点${x}_{i,j}$与${u}_{i,j}'$（即${u}_{i,j}$在$G'$的对应点）构成的边，所以有${T}'= \left\{{x}_{i,j}{u}_{i,j}':1\le i\le l,1\le j\le {d}_{i}\right\}$.

此归约显然可以在多项式时间内完成，下文证明其正确性.

首先，设$S\subseteq V$是一个$G$的解. 由于$S$中没有关键点，因此其中的每一个点都有在$G'$中的对应点. 设$S$对应在$G'$中的点集为${S}'=\{{v}':v\in S\}$. 注意到，$S$覆盖了$G$中所有经过${t}_{i}{u}_{i,j}$的环（$1\le j\le {d}_{i}$）. 所以$S'$覆盖了$G'$中所有经过关键边${x}_{i,j}{u}_{i,j}'$的环. 这说明了$S'$为$G'$的一个解；反之，设$S'$为$G'$的一个解. 若$S'$经过某顶点${x}_{i,j}$，则${(S}'\setminus \left\{{x}_{i,j}\right\})\cup \{{u}_{i,j}'\}$也为$G'$的一个解，若不然，则存在一个经过关键边的环$C$包含${x}_{i,j}$. 由于${u}_{i,j}'$在解$S'$中，因此$C$不可能包含边${x}_{i,j}{u}_{i,j}'$. 那么$C$中必然包含长度为2的路${x}_{i,a}{x}_{i,j}{x}_{i,b}$（$a\ne j$且$b\ne j$）. 由于${x}_{i,a}$和${x}_{i,b}$相连，因此$C\backslash \left\{{x}_{i,j}\right\}$中的点也构成一条经过关键边的环，这与${S}'$是$G'$的一个解矛盾. 所以，$G'$中存在一个大小等于${S}'$且不包含${x}_{i,j}$（$1\le i\le l,1\le j\le {d}_{i}$）的解${S}{''}$. ${S}{''}$对应在$G$中的点集记作$S=\{v:v'\in S''\}$. 因为$G'$中任何一个经过边${x}_{i,j}{u}_{i,j}'$的环都会包含$S''$中的点，所以$G$中任意一个经过${t}_{i}{u}_{i,j}$的环必然包含$S$中的点. 故而得出$S$为$G$中的一个解. 这意味着实例$I$为真当且仅当实例${I}'$为真.

综上所述，该定理成立. 证毕.

小结：R-ESFES是唯一一个NP难的子集反馈边集问题. 在子集反馈边集问题中，R-ESFES较为特殊，没有已知的关于R-ESFES与子集反馈点集问题之间保持解集大小或关键集大小的归约. 所以，求解R-ESFES需要单独设计针对性的高效算法. 而3类子集反馈点集问题之间存在的紧密的归约关系，大量研究主要集中在SFVS问题上，且求解SFVS的算法也通常能适用于求解其他2类子集反馈点集问题.

2.3   有向图上的反馈集与子集反馈集问题

有向图上的反馈点集问题DFVS与反馈边集问题DFAS都是NP难的^[16]，并且它们都属于Karp^[16]于1972年给出的21个经典的NP完全问题. DFVS和DFAS之间可以互相多项式时间归约并保持解集大小和关键集大小均不变^[17]. 具体地，对于DFVS到DFAS的归约，可以将每一个顶点替换为1条有向边，使得有向边的末端点连接原顶点的出边顶点，而有向边的起始端点连接原顶点的入边顶点；对于DFAS到DFVS的归约，将每条有向边替换为1个顶点，若2条有向边首尾相连时，则对应的顶点按照相同方向相连. 针对6类子集反馈集问题，基于同样的构造策略，可以证明DSFVS，DASFVS，DASFAS三者以及DSFAS，R-DSFVS，R-DASFAS三者均两两可互相归约，并且保持解集和关键集大小均不变^[17,20].

图2展示了无向图上的2个反馈集问题与6个子集反馈集问题的归约关系. 有向图上的子集反馈集问题的限制版和非限制版之间存在保持解集大小不变的多项式时间归约，虽然在相关文献中未提及相应结论，但可以沿用文献[17]中的归约思想. 本文定理2给出了完整的归约构造.

图  2  有向图上反馈集与子集反馈集问题的归约关系

Figure  2.  Reductions among feedback set and subset feedback set problems in directed graphs

下载: 全尺寸图片 幻灯片

定理2. DSFVS可以多项式时间归约到R-DSFVS并保持解集和关键集大小不变.

证明. 设DSFVS的实例为$I=\left(G=\left(V,E\right),T,k\right)$，$I$为真当且仅当$G$中存在大小不超过$k$的解. 现构造R-DSFVS的实例${I}'=\left({G}'=\left({V}',{E}'\right),{T}',{k}'=k\right)$，${I}'$为真当且仅当${G}'$中存在大小不超过${k}'=k$的解. 将每一个$G$中的点替换为1条有向边，得到有向图${G}'=\left({V}',{E}'\right)$，其中${V}'=\left\{{v}',{v}'':v\in V\right\}$，边集${E}'=\left\{{v}''{u}':vu\in E\right\}$. 令${G}'$中的关键点为$G$中关键点对应的边的起始点构成的顶点集${T}'=\{t':t\in T\}$.

此归约显然可以在多项式时间内完成，下文证明其正确性.

我们的论证需要以下事实：由于$G'$中的点要么出度为1要么入度为1，因此$G'$中的环必然形如$({v}_{1}',{v}_{1}'',{v}_{2}',{v}_{2}'',… ,{v}_{r}'{,v}_{r}'')$，并且和$G$中的$({v}_{1},{v}_{2},… ,{v}_{r})$一一对应.

设$S\subseteq V$是一个$G$的解，令${S}'=\{{v}'':v\in S\}$. 显然经过$G'$中的某一关键点$t''$的环，必然经过边${t}'{t}''$，从而其在$G$中对应的环必然经过$t$. 这说明了$S'$是$G'$的一个解. 反之，根据定义，$G'$中的解$S'$不允许包含$\{{t}':t\in T\}$. 令$S=\{v:{v}'\in S'\}\cup \{v:{v}''\in S'\}$，显然有$\left|S\right|=\left|{S}'\right|$. 注意到经过$G$中的某一关键点$t$的环，其在$G'$中对应的环必然经过边${t}'{t}''$，从而必然经过${t}'$. 这说明了$S$是$G$的一个解. 这说明实例$I$为真，当且仅当实例${I}'$为真.

综上所述，该定理成立. 证毕.

结合2.1节的阐述可得：也存在DSFAS到DASFAS并且保持解集大小不变的多项式时间归约. 6类有向图上的子集反馈集问题两两之间的关系便可以完全得出.

小结：有向图上的6个版本的子集反馈集问题有着非常强的等价性. 针对某一版本的算法通常都可以很好地适用于其他版本. 现有的研究主要集中于DSFVS或DSFAS上.

2.4   反馈集与子集反馈集问题的快速算法

本节将按照无向图和有向图的分类方式，进一步介绍求解反馈集问题与子集反馈集问题的快速算法的研究现状.

在无向图上，FVS可在${3.46}^{k}{n}^{O\left(1\right)}$时间内求解^[21]，其中$k$为解集大小. 该算法使用了最大度分支（high-degree branching）技术，而算法的复杂度分析采用了度量治之（measure and conquer）技术. 此外，Fomin等人^[22]提出了一类“覆盖问题”的精确算法框架：基于时间复杂度为${c}^{k}{n}^{O\left(1\right)}$的算法，可以得到一个时间复杂度为${(2-{c}^{-1})}^{n}{2}^{o\left(n\right)}$的算法. 这意味着FVS可在$O\left({1.711}^{n}\right)$时间内求解. 与之相比，存在运行时间为${2.7}^{k}{n}^{O\left(1\right)}$的概率算法^[23]更快求解FVS. 同理，使用Fomin等人^[22]提出的精确算法框架，存在时间复杂度为$O\left({1.630}^{n}\right)$的概率算法求解FVS. 在近似算法领域，存在近似率为$2-2/(3\varDelta -2)$的近似算法^[24]，其中$\varDelta$是输入图中的最大度，这意味着FVS存在近似率为$2$的近似算法.

在有向图上，存在求解DFVS的时间复杂度为$k!{4}^{k}{n}^{O\left(1\right)}$以及$O\left({1.997\; 7}^{n}\right)$的算法^[25-26]. 并且DFVS存在近似率为$O\left(\mathrm{log}k\;\mathrm{log}\;\mathrm{log}k\right)$近似算法^[27-28]. 针对DFAS，目前最快的算法是运行时间为$O\left({2}^{n}\right)$的动态规划（dynamic programming）算法^[29-30]，该算法需要指数级大小的空间.

考虑任意一种NP难的非限制版本的子集反馈集问题（DSFAS除外）. 由于关键集就是一个合法解集，因此最优解的大小不超过$l$，所以暴力检查图中所有大小不超过$l$的子集便可以求得最优解，进而这些非限制版本的子集反馈集问题可以在$O\left({n}^{l}\right)$的时间内求解. 所以当$l$为常数时，它们都可在多项式时间内求解.

相比之下，对于限制版本的子集反馈集问题，关键点集大小为常数时，其计算复杂性会更加有趣一些，许多研究工作聚焦于此. 表3给出了限制版子集反馈集问题在关键集大小为常数时的计算复杂性.

表  3  子集反馈集问题在$\mathit{l}$为常数时的计算复杂性

Table  3.  Complexity of Subset Feedback Set Problem When $\mathit{l}$ is a Constant

问题	$l$的值	计算复杂性
R-SFVS	固定的$l\ge 1$	NP难[18]
R-SEFES	$l=1$	$\mathrm{P}$[19]
	固定的$l\ge 2$	NP难 [19]
R-DSFVS	$l=1$	$\mathrm{P}$[17]
	固定的$l\ge 2$	NP难 [17]
R-DASFAS	$l=1$	$\mathrm{P}$[17]
	固定的$l\ge 2$	NP难[17]

下载: 导出CSV 

| 显示表格

在无向图上，当关键点集大小$l=1$时，R-SFVS等价于经典的节点多路割问题（node multiway cut problem）^[18]，从而说明即使在$l=1$的情况下，R-SFVS也是NP难的. 在节点多路割问题中，给定一个点集（终端集），要求求出大小不超过$k$的点割（separator），使得删去割集后，终端两两不在同一连通块中. 由此可得，当$l=1$时，直接调用多路割的算法，R-SFVS可在${2}^{k}{n}^{O\left(1\right)}$^[31]和${1.5}^{n}{2}^{o\left(n\right)}$^[22]的时间内求解，此算法基于线性规划（linear programming）技术. 同时存在1.3438近似率的近似算法^[32]，该算法基于线性规划对偶问题，而其近似率的分析依赖于计算机辅助.

在无向图上，当关键集大小$l=1$时，R-ESFES等价于最小边割问题（minimum edge cut problem）^[17]，因此是多项式时间可解的. 当关键点集大小$l\ge 2$时，则是NP难的^[19]. 在最小边割问题中，输入1个无向图和1个顶点对，计算大小不超过$k$的边割使得删去边割以后这2个顶点不在同一连通块中. 因此，当$l=1$时，R-ESFES可以在${m}^{1+o\left(1\right)}\mathrm{时}\mathrm{间}$内求解^[33]. 而$l\ge 2$时，Xiao等人^[19]给出了时间复杂度为${2}^{O\left(k\mathrm{log}k\right)}{n}^{O\left(1\right)}$的算法. 针对SFVS，Even等人^[18]在2000年给出了求解SFVS的近似率为8的近似算法. 而在2018年，Iwata等人^[34]给出了SFVS的基于线性规划技术的算法，该算法时间复杂度为单指数${4}^{k}{n}^{O\left(1\right)}$. 结合Fomin等人^[22]提出的技术，可以获得${1.75}^{n}{2}^{o\left(n\right)}$时间复杂度的精确算法.

有向图上的子集反馈集问题可以互相归约且保持解集大小不变. 针对有向图上的子集反馈集问题，Even等人^[17,35]给出了近似率分别为$O\left(\mathrm{log}k\;\mathrm{log}\;\mathrm{log}k\right)$和$O\left(\mathrm{log}l\;\mathrm{log}\;\mathrm{log}l\right)$的2个近似算法.

有向图上限制版子集反馈集问题R-DSFVS和R-DASFAS，可以互相归约且保持解集大小和关键集大小不变. 当$l=1$时，2类问题均为多项式可计算的，可以使用最大流算法求解^[17]；而$l\ge 2$时，则是NP难的. 该结论在文献[17]中提到，但未给出证明. 考虑到该证明并非平凡的，本文在定理3中补充了此证明. 证明中使用2个终端对的有向节点多割问题（directed node multicut problem）的NP难性^[36]的证明技巧. 在节点多割问题中，给定一个有向图和一个点对集（终端对集），要求求出大小不超过$k$的点割，使得去掉割集后，任意终端对都不在同一连通块中.

定理3. 当关键集大小$l\ge 2$时，R-DSFVS和R-DASFAS均为NP难的.

证明. 由于R-DSFVS和R-DASFAS等价，并且保持解集大小和关键集大小不变，只需考虑R-DSFVS的NP难性. 此外，对于任意的$l > 2$，均可由$l=2$的特例归约得到（增加$l-2$个孤立关键点即可）. 所以只需证明$l=2$的情形.

使用3个关键点的无向图节点多路割问题进行归约. 多路割问题的一个实例为$I=\left(G=\left(V,E\right),T,k\right)$，其中$G$为无向图，$T=\left\{a,b,c\right\}\subseteq V$包含3个终端点，$I$为真当且仅当存在大小不超过$k$的点割$S\subseteq V\backslash T$，使得$a，b，c$在$G-S$中属于不同的连通块. 现构造R-DSFVS的实例${I}'=\left({G}'=\left({V}',{E}'\right),{T}',{k}'=k\right)$，${I}'$为真当且仅当${G}'$存在大小不超过$k$的解.

第1步. 复制原图$G$中各点得到集合$\left\{{v}':v\in V\right\}$，那么$a，b，c$在${G}'$都有对应的顶点${a}'，b'，c'$，它们均不再是关键点.

第2步. 若$u$和$v$在$G$中相连，新增2个2度点${x}_{vu}'$和${y}_{vu}'$使得$v'{x}_{vu}'$，${x}_{vu}'u'，u'{y}_{vu}'$，${y}_{vu}'v'$为有向边，其结构如图3所示.

图  3  节点多路割到R-DSFVS的多项式时间归约示意图

Figure  3.  Illustrations of the polynomial-time reduction from node multiway cut to R-DSFVS

下载: 全尺寸图片 幻灯片

第3步. 取关键点集$T'=\{{t}_{1}',{t}_{2}'\}$满足$a'{t}_{1}'$，$b'{t}_{1}'，{t}_{1}'c'， b'{t}_{2}'，{t}_{2}'a'$为有向边，其结构如图3所示.

第4步. 对$a'，b'，c'$分别再复制$k$份后得到集合${\{{a}_{i}',{b}_{i}',{c}_{i}'\}}_{1\le i\le k}$，满足${a}_{i}'，{b}_{i}'，{c}_{i}'$的出入边邻居分别等于$a'，b'，c'$的出入边邻居. 最终得到${G}'=\left({V}',{E}'\right)$，其中${V}' = \{{v}' : v\in V\} \cup \{{x}_{vu}',{y}_{vu}' : vu\in E\} \cup \{{t}_{1}',{t}_{2}'\} \cup \{{a}_{i}',{b}_{i}',{c}_{i}' : 1 \le i \le k\}$，且${E}'={E}_{1}'{\cup E}_{2}'\cup {E}_{3}'$ ，这里有

1）${E}_{1}'=\left\{{v}'{x}_{vu}',{x}_{vu}'{u}',u'{y}_{vu}',{y}_{vu}'v':vu\in E\right\}$；

2）${E}_{2}'=\left\{{a}'{t}_{1}',{b}'{t}_{1}',{t}_{1}'{c}',{b}'{t}_{2}',{t}_{2}'{a}'\right\}$；

3）${E}_{3}'\;=\;\{{v}'{z}_{i}',{z}_{i}'{w}':z\in \left\{a,b,c\right\},1\le i\;\le\; k\mathrm{且}{v}'{z}',\;{z}'{w}'\in {E}_{1}'{\cup E}_{2}'\}$.

此归约显然可以在多项式时间内完成，下文证明其正确性. 论证需要使用以下性质：

1）构造中的第2步将每一条无向边替换为2条反向的2长路. 可见，若$({v}_{1},{v}_{2},… ,{v}_{r})$为图$G$中的1条无向路，则$G'$存在1对有向路

和

并且它们之间存在一一对应关系.

2）第4步构造使得若$G'$中有1条有向路经过${a}_{i}'$，则将${a}_{i}'$替换为${a}_{j}'$也为1条有向路. 这意味着$G'$中的任意一个最小解集不可能包含${\{{a}_{i}',{b}_{i}',{c}_{i}'\}}_{1\le i\le k}$和$\{a',b',\mathrm{c}'\}$.

3）若$G'$的一个解包含2度点${x}_{vu}'$或${y}_{vu}'$，则将其替换为其邻居$v$或$u$，得到的集合也为$G'$的一个解.

设$S'\subseteq V'$是一个$G'$的一个最小解. 根据定义，$S'$不会包含关键点，也不会包含新增加的2度点，所以$S'$中每一个点均存在$G$中对应点，这些点构成集合$S=\{v:v'\in S\}$. 由于在$G'-S'$中没有经过${t}_{2}'$的环，所以在$G-S$中没有$a$到$b\mathrm{以}\mathrm{及}b$到$c$的路；又因为$G'-S'$中没有经过${t}_{1}'$的环，所以在$G-S$中没有$a$到$c$的路，从而得出$S$为$G$的一个解.

反之，设$S\subseteq V$是一个$G$的最小解，根据节点多路割的定义，$S$不会包含3个终端点$a,\;b,\;c$. 因此$S$中每一个点存在$G'$中对应点，这些点构成集合$S'=\{v':v\in S\}$. 注意到，在$G-S$中$a$、$b$和$c$在不同的连通块里. 因此，$G'-S'$中，${t}_{1}'$和${t}_{2}'$在不同的强连通块中. 这说明了没有经过关键点的环，故而$S'$为$G'$的一个解. 从而可以得出实例$I$为真当且仅当实例${I}'$为真.

综上所述，该定理成立. 证毕.

求解有向图上的子集反馈集问题更加复杂而困难，直至近几年才有研究者提出了少量的非平凡算法. 2015年，针对DSFVS，Chitnis等人^[20]提出了目前速度最快、运行时间为${2}^{O\left({k}^{3}\right)}{n}^{O\left(1\right)}$的算法. 接着，Chitnis等人^[37]在2017年给出了包括DSFVS在内的一系列子集版本问题的求解算法，基于时间复杂度为$O\left({1.997\; 7}^{n}\right)$的SFVS的求解算法^[26]，证明了DSFVS可以在$O\left({1.9993}^{n}\right)$时间内求解.

小结：反馈集问题的精确算法经过大量研究，其时间复杂度被多次改进，目前最快的以解集大小为参数的算法，是时间复杂度为${2.7}^{k}{n}^{O\left(1\right)}$的随机算法，首次突破了${3}^{k}$. 此算法是否能够去随机化是许多学者关心的课题. 无向图上的反馈集问题均已有常数近似率的近似算法；与之相比，有向图上的反馈集与子集反馈集问题目前仅已知可以达到$O\left(\mathrm{log}k\;\mathrm{log}\;\mathrm{log}k\right)$近似. 此外，除了DSFVS以外，有向图上其他版本的子集反馈集问题目前也尚未有高于$O\left({2}^{n}\right)$的精确算法.

3.   特殊图上的反馈集与子集反馈集问题的计算复杂性

特殊图上的反馈集与子集反馈集问题的计算复杂性也有大量的研究积累. 在某些场景中，问题的输入图具有一些特定的性质. 因此，特殊图上的反馈集问题通常会比一般图上的问题更容易求解. 所以研究特殊图上的反馈集与子集反馈集问题具有更实际的价值. 常见的有向图图类包括度有界图（degree-bounded graph）、平面图（planar graph）和竞赛图（tournament）等图类；常见的无向图图类包括度有界的图、平面图、相交图（intersection graph）、禁止图（forbidden graph）、二部图（bipartite graph）等图类. 本节将按照不同图类讨论反馈集和子集反馈集问题关于计算复杂性的研究进展.

3.1   度有界的图类

本节介绍无向和有向的度有界图上反馈集问题的计算复杂性. 当一个图中所有顶点的度数不超过某个常数d时，该图被称为一个d度图. 6度图上FVS和DFVS的NP难性可直接由3度图上的点覆盖问题（vertex cover problem）的NP难性得到. 在点覆盖问题中，给定一个无向图和一个正整数$k$，目标为找到一个大小不超过$k$的点集，使得删除这些点后，剩下的图中无边. 考虑点覆盖的任意一个实例，将其中的每一条边添加一个2度点连向此边的2个端点，便得到了一个6度无向图上FVS的实例. 对每条边及其对应的2度点构成的三角形定向便得到了6度有向图上DFVS或DFAS的实例^[38].

对有向图而言，当输入图的最大入度或最大出度为1时，图中的每一个强连通块最多包含1个环，因而可在线性时间内求解DFVS和DFAS. 另一方面，若将SFVS的输入图中的度数至少为4的点替换成一些3度点构成的路，其中每个点的入度为1且出度为2或者入度为2且出度为1的点. 如此归约便进一步证明了在最大入度和最大出度均为2的有向图上的DFVS是NP难的^[38].

对无向图而言，Speckenmeyer^[39]进一步证明了4度平面图上的FVS也是NP难的. 然而，3度图上FVS是否是多项式时间可解直到1988年才得到肯定的回答. Ueno等人^[40]将无向3度图上的FVS归约到拟阵奇偶性问题（matroid parity problem）. 由于图拟阵的拟阵奇偶性问题可在$O\left(nm{\mathrm{l}\mathrm{o}\mathrm{g}}^{6}n\right)$时间内求解^[41]，故而无向3度图上的FVS可以在$O\left({n}^{2}{\mathrm{l}\mathrm{o}\mathrm{g}}^{6}n\right)$时间内求解（3度图的边数和点数为线性关系）. 至此，度有界的图上的FVS的复杂度分类被完全解决. 表4给出了具体的计算复杂性. 对于子集反馈集问题，其在3度无向图上的NP难性仍然未知.

表  4  度有界的图上的反馈集问题的计算复杂性

Table  4.  Complexity of Feedback Set Problems in Degree Bounded Graphs

问题	图类	计算复杂性
FVS	3度图	O(n2log6n)[40-41]
FVS	4度图	NP难[39]
DFVS	最大出度为1的有向图	$O\left(n\right)$
DFAS	最大出度为1的有向图	$O\left(n\right)$
DFVS	最大出入度为2的有向图	NP难[38]
DFAS	最大出入度为3的有向图	NP难[38]

下载: 导出CSV 

| 显示表格

3.2   平面图图类

早在1978年，Yannakakis^[42]证明了有向平面图上的FVS是NP难的. 由于点覆盖到反馈集问题的归约保持平面性，所以无向平面图上的FVS也为NP难的. 最大入度和最大出度均不低于3时，平面图上的DFVS也是NP难的^[38]. 需要指出的是，虽然一般有向图上的DFVS和DFAS可互相归约，但是在平面图上它们的计算复杂性不同. 事实上，基于线性规划的对偶性^[43]，平面图上DFAS是可以在$O\left({n}^{2.5}\mathrm{log}n\right)$^[44]时间内求解的. 对无向图而言，Speckenmeyer^[39]在其博士论文中进一步证明无向平面4度图上的FVS也是NP难的.

此外，即使是平面二部图上，FVS或DFVS依然是NP难的. 归约操作是将每条边替换为1个2度点连接此边的2个端点，这个操作不影响输入图的平面性，也不改变最小反馈点集的大小. Cavallaro^[45]在其硕士论文中研究了输入图具有哈密顿性时的FVS，证明了即使已知输入图的哈密顿序列，四正则图上的FVS依然是NP难的.

FVS在补平面图上是多项式时间可计算的. 如果一个图的补图是平面图，则称其为补平面图（coplanar graph）. 根据四色定理^[46-47]，补平面图的点集可以划分为4个点子集，使得每一个点子集构成的导出子图都是一个团，且此划分可在平方级的时间内找到^[48]. 因此，补平面图上最大导出森林（maximum induced forest）的大小不会超过8个顶点. 所以，补平面图上的FVS可通过枚举所有大小不超过8的点集，从而在多项式时间内求解. 事实上，此算法可以进行简单地扩展来求解补平面图上的SFVS. 定理4给出了求解补平面图上SFVS的一个多项式时间算法. 表5给出了平面图和补平面图上反馈集与子集反馈集问题的计算复杂性.

表  5  平面图上的反馈集和子集反馈集问题的计算复杂性

Table  5.  Complexity of Feedback Set and Subset Feedback Set Problems in Planar Graphs

问题	图类	计算复杂性
FVS	3度平面图	O(n2log6n)[40-41]
FVS	4正则哈密顿平面图	NP难[45]
SFVS	补平面图	P [定理4]
DFVS	最大出入度为3的平面有向图	NP难[38]
DFAS	平面图	O(n2.5logn)[43-44]

下载: 导出CSV 

| 显示表格

定理4. 补平面图上的SFVS可在多项式时间内求解.

证明. 根据四色定理^[46-47]，补平面图$G=(V,E)$的点集有一个4划分$V={V}_{1}\cup {V}_{2}\cup {V}_{3}\cup {V}_{4}$使得$G\left[{V}_{i}\right]$（$i=1, 2,3,4$）为一个团. 此划分可在$O\left({n}^{2}\right)$时间^[48]内找到. 对于每一个导出子图$G\left[{V}_{i}\right]$，如果${V}_{i}$包含关键点，则对于$G$的任意一个解$S$，要么满足$T\cap {V}_{i}\subseteq S$，要么${V}_{i}\setminus S$的大小最多为2，否则$G\left[{V}_{i}\right]-S$中必然存在经过关键点的环.

在第1步中，每一个${V}_{i}$上枚举了至多${\left|{V}_{i}\right|}^{2}+1$个子集：一种情况是将满足$T\cap {V}_{i}$的点全部放入解集中；其余至多${\left|{V}_{i}\right|}^{2}$种情况是枚举${V}_{i}\setminus S$剩下的至多2个顶点，这一步的运行时间为$O\left({n}^{8}\right)$. 当算法的第1步完成时，每一个${V}_{i}$中剩余点要么大小不超过2，要么不包含任何关键点. 若每一个${V}_{i}$都包含关键点，则剩下的图的大小为常数，可以在常数时间内求解. 否则，至少有1个${V}_{i}$不包含关键点，此时图中的最小子集反馈集的大小不会超过6，因为图中最多只有6个关键点.

第2步，此步骤只需要消耗$O\left({n}^{6}\right)$的时间枚举大小为6的点集，便可以求得最小的子集反馈集的大小，从而可以判断解集大小. 算法的总耗时为$O\left({n}^{14}\right)$.

综上所述，该定理成立. 证毕.

3.3   竞赛图图类

竞赛图是一个由完全图（complete graph）进行边定向得到的有向图. 二部竞赛图（bipartite tournament）则是一个由完全二部图进行边定向得到的有向图. 竞赛图模型可以用于刻画循环制比赛的胜负关系. 竞赛图上的反馈点集和反馈边集常用于比赛的排名算法^[3-4].

竞赛图上的DFVS的NP难性在1989年已被证明^[49]. 然而，直到21世纪初，竞赛图上的DFAS以及二部竞赛图上的DFVS和DFAS的计算复杂性才得到了解决. 值得强调的是，在竞赛图或二部竞赛图中，DFVS与DFAS之间没有找到显然的多项式时间归约关系，因而其NP难性要分别进行考虑.

2002年，Cai等人^[50]证明了二部竞赛图上的DFVS是NP难的. 此后，3个独立的研究^[51-53]分别使用不同的归约思想证明了竞赛图上的DFAS是NP难的. 最后，Guo等人^[54]证明了二部竞赛图上的DFAS是NP难的. 表6给出了竞赛图和二部竞赛图上反馈集问题和子集反馈集问题的计算复杂性.

表  6  竞赛图和二部竞赛图上的反馈集和子集反馈集问题的计算复杂性

Table  6.  Complexity of Feedback Set and Subset Feedback Set Problems in Tournaments and Bipartite Tournaments

问题	图类	计算复杂性
DFVS	竞赛图	NP难[49]
DFAS	竞赛图	NP难[51-53]
DFVS	二部竞赛图	NP难[51]
DFAS	二部竞赛图	NP难[54]

下载: 导出CSV 

| 显示表格

3.4   相交图图类

相交图是一类重要的无向图论模型，由一组集合（通常为几何图形）生成，每一个集合对应图中的1个顶点，2个顶点之间存在一条边当且仅当它们所对应的集合相交非空. 经典的相交图包括补比较图（co-comparability graph）、梯形图（trapezoid graph）、置换图（permutation graph）、弧线图（circular arc graph）、弦图（chordal graph）、圆图（circle graph）、区间图（interval graph）、分裂图（split graph）等.

在相交图模型上求解FVS问题的算法可以追溯到1985年，Brandstädt等人^[55-56]提出了一个运行时间为$O\left({n}^{6}\right)$的动态规划算法来解决置换图上的FVS. $n$阶置换图由一个$n$阶置换确定：每个顶点代表置换中的1个元素，若2个元素的置换形成逆序对，则它们对应的顶点之间存在一条边. Brandstädt^[57]随后改进了此算法，将时间复杂度降低至$O\left(nm({n}^{2}-m)\right)$. Liang^[58]提出的一个运行时间为$O\left(nm\right)$的动态规划算法是目前已知最快的置换图上FVS的求解算法.

梯形图是由2条平行线之间的梯形构成的相交图. 置换图是梯形图的一个子类. Honma等人^[59]通过枚举极大团并计算长度为4的导出环的方式，提出了一种求解梯形图上FVS的算法，该算法运行时间为$O\left({n}^{2.68}+\gamma n\right)$，其中$\gamma$为所有极大团的枚举长度. 这里强调，$\gamma$关于点数$n$可能是指数增长的. 此外，置换图的一个子类，二部梯形图（bipartite trapezoid graph），也是一个重要的相交图类. 二部梯形图上的FVS可在线性时间内求解^[60].

补比较图是由2条平行线之间（一条直线到平行的另一条直线）的连续曲线构成的相交图. 梯形图是补比较图的一个子类. Coorg等人^[61]首先给出了一个运行时间为$O\left({n}^{4}\right)$的算法，用于求解补比较图上的FVS. 随后，Liang等人^[62]基于动态规划提出了一个运行时间为$O\left({n}^{2}m\right)$的算法.

圆-$d$-拱形图（circle $d$-gon graph）是圆-$d$-拱形（circle $d$-gon）构成的相交图，圆-$d$-拱形是指一个圆中不超过$d$个两两不相交的弦形成的中间区域. 针对固定的正整数$d$，Gavril^[63]采用动态规划技术证明了圆-$d$-拱形图上的FVS可以在$O\left({n}^{2d+5}\right)$时间内求解. 圆-$d$-拱形图包含了众多特殊图领域内常见的相交图类，包括梯形图、区间图、弧线图等. 特别地，圆-$1$-拱形图也称为圆图，而圆-$2$-拱形图也称为圆-梯形图（circle-trapezoid graph），它们分别可在$O\left({n}^{7}\right)$和$O\left({n}^{9}\right)$时间内求解. 在这些图类上SFVS的可解性结果较少，Papadopoulos等人^[64]给出了一个运行时间为$O\left({m}^{3}\right)$的动态规划算法用于求解区间图上的SFVS，该算法需要维护3个与终端集相关的集合的大小以完成状态转移. 基于此算法，进一步提出了求解弧线图和置换图上SFVS的算法，时间复杂度分别为$O\left({n}^{4}\right)$和$O\left({m}^{3}\right)$.

弦图是由树上的子树构成的相交图. 弦图上的FVS的高效算法也是早期的研究之一. 早在1987年，Yannakakis等人^[65]通过研究弦图上的可染色子图问题，得到了基于树分解上动态规划技术的多项式时间算法. 经过一些简单的状态预处理，该算法可以在$O\left({n}^{4}\right)$时间内求解弦图上的FVS. 区间图和分裂图分别是路（path）和星图（star graph）上的子树构成的相交图. 区间图和分裂图都是弦图的子图类，因此FVS在这些子图也是多项式时间可求解的. 需要强调的是，分裂图是弦图和补弦图的交类，根据分裂图的结构，文献[65]中的算法可以在平方级的时间内求解分裂图上的FVS. 最后，Lu等人^[66]提出了区间图上的FVS上的线性时间动态规划算法. 但对子集反馈集而言，Fomin等人^[67]证明了弦图甚至分裂图上的SFVS和R-SFVS都是NP难的.

由于区间图甚至弦图上的R-SFVS可以在立方级的时间内归约到点覆盖问题^[68]，并且区间图上的点覆盖可在线性时间内求解^[69]，因此R-SFVS在区间图上便可以在立方级的时间内求解. 表7给出了相交图上反馈集问题和子集反馈集问题的计算复杂性.

表  7  相交图上的反馈集和子集反馈集问题的计算复杂性

Table  7.  Complexity of Feedback Set and Subset Feedback Set Problems in Intersection Graphs

问题	图类	计算复杂性
FVS	置换图	O(nm)[58]
SFVS	置换图	O(m3)[64]
FVS	补比较图	O(n2m)[62]
FVS	圆图	O(n7)[63]
FVS	圆-d-拱形图	O(n2d+5)[63]
SFVS	弧线图	O(n4)[64]
FVS	弦图	O(n4)[65]
FVS	分裂图	O(n2)[65]
SFVS	弦图/分裂图	NP难[67]
R-SFVS	弦图/分裂图	NP难[67]
FVS	区间图	O(m)[66]
SFVS	区间图	O(n3)[64]
R-SFVS	区间图	O(n3)[68-69]

下载: 导出CSV 

| 显示表格

3.5   禁止图图类

若一个图$H$不是一个图$G$的导出子图，则称图$H$是图$G$的禁止子图或禁忌子图（forbidden subgraph）. 给定一个子图集$\mathcal{H}$，以$\mathcal{H}$中的子图为禁止子图所构成的禁止图图类称为$\mathcal{H}$-free的. $\mathcal{H}$中禁止子图的个数可以是无限多个. 例如，森林（forest）是${\left\{{C}_{p}\right\}}_{p\ge 3}$-free图，有无限多个禁止子图，其中${C}_{p}$表示长度为$p$的环. 包括置换图、补比较图、区间图、弦图在内的相交图均可表示为具有无限多禁止子图的图类.

AT-free图是一类更广的图类，补比较图是其子类. AT-free有无限多个禁止子图. 一个图是AT-free图当且仅当这个图不包含星状三元组(asteroidal triples），这里星状三元组是指满足如下性质的3个顶点：任意2点间均存在不经过第3点的邻居的路径. Kratsch等人^[70]提出了一个求解AT-free图上FVS的算法. 该算法通过计算和维护2种局部结构的大小来计算最大导出森林的大小，其运行时间为$O\left({n}^{8}{m}^{2}\right)$.

有单个禁止子图的禁止图上的FVS问题目前已展开了充分的研究. 一方面Poljak^[71]证明了围长（girth）至少为$3$的图上的FVS是NP难的；这意味着如只要$H$包含了任何一个环${C}_{r}（r\ge 3）$，则$H$-free图上的FVS必为NP难的；另一方面，Munaro^[72]证明了线图（line graph）上的FVS也是NP难的；这蕴含着如果$H$包含了完全二部图${K}_{1,3}$，则$H$-free图上的FVS也是NP难的. 综上可得，若$H$-free图上的FVS存在多项式时间算法，那么$H$必然为线性森林（linear forest），即一些不相交的路构成的森林. 若一个线性森林$G$是由${s}_{1}+{s}_{2}+… +{s}_{r}$条路组成，其中长度为$i$的路有${s}_{i}$个（$1\le i\le r{\mathrm{且}s}_{i}\ge 0$），则记

最近几年，线性森林上的FVS的分类工作逐步展开. 已知置换图上的FVS是多项式时间可计算的，故而${P}_{4}$-free图上的FVS是多项式时间可计算的. 此后，对于任意正整数$s\ge 0$，$(s+1){P}_{2}$-free图^[73]、$(s{P}_{1}+{P}_{3})$-free图^[74]和${P}_{5}$-free图^[75]上的FVS先后被证明是多项式时间可解的. 目前的最好结果是Paesani等人^[76]所证明的结果：$(s+1){P}_{3}$-free图和$(s{P}_{1}+{P}_{5})$-free图上的FVS均可在多项式时间内求解；并且对于所有线性森林$H$,$H$-free图上的FVS问题都可以在${n}^{{\left(\mathrm{log}n\right)}^{O\left(1\right)}}$时间内计算. 然而，当$H$是${P}_{6}$或$s{P}_{2}+{P}_{4}$的超集时，$H$-free图上的FVS是否存在多项式时间算法仍是未知的^[76].

幸运的是，线性森林上SFVS的计算复杂性分类工作已经完成. （显然，非线性森林上的SFVS必然是NP难的. ）Paesani等人^[77]证明了，线性森林$H$是$2{P}_{1}+ {P}_{4}$的子图时，$H$-free图上的SFVS是多项式时间可计算的，否则便是NP难的. 表8给出了各类禁止图上反馈集和子集反馈集问题的计算复杂性.

表  8  禁止图图类上反馈集和子集反馈集问题的计算复杂性

Table  8.  Complexity of Feedback Set and Subset Feedback Set Problems in Forbidden Graphs

问题	图类	计算复杂性
FVS	AT-free	O(n8m2)[70]
FVS	$H$-free (${C}_{r}\subseteq H,r\ge 3)$	NP难[71]
FVS	线图	NP难[72]
FVS	$(s{P}_{1}+{P}_{5})$-free ($s\ge 0$)	P[73-76]
FVS	$s{P}_{3}$-free ($s\ge 1)$	P[74,76]
SFVS	$(2{P}_{1}+{P}_{4})$-free	P[77]
SFVS	$H$-free $(H\nsubseteq 2{P}_{1}+{P}_{4}$)	NP难[77]

下载: 导出CSV 

| 显示表格

3.6   二部图图类

本节将介绍一些二部图图类上反馈集问题的计算复杂性分类结果. 本节所介绍的二部图均用符号$G=(A\cup B,E)$表示，其中$A$和$B$分别表示二部图的2部顶点集，$E$表示二部图的边集.

在一般的二部图上，FVS和DFVS均是NP难的. 通过将无向图上的任意一条边替换为一个二度点，然后将原边的2个端点与这个二度点相连，可以将一般图无向图上的FVS归约到二部图上的FVS. 然而，在补二部图（co-bipartite graph）上的FVS是多项式时间可解的，这是因为补二部图是补比较图的子类. 值得注意的是，Papadopoulos等人^[64]证明了补二部图上的极小子集反馈点集数量不会超过$22{n}^{4}$. 此外，他们进一步给出了一个时间复杂度为$O\left({n}^{4}\right)$的极小子集反馈点集的枚举算法，这也能够说明了补二部图上的SFVS是多项式可解的.

路凸二部图（path convex bipartite graph），简称凸二部图（convex bipartite）是指一类满足以下性质的二部图：存在以$A$为顶点的路$G'=(A,E')$，使得$B$中任意顶点的邻居在$G'$中连通. 1997年，Liang等人^[62]证明了凸二部图上的FVS可在

时间内求解. 后续的一些可解性工作基本上都是对此算法进行的推广.

三元凸二部图（triad convex bipartite graph）是凸二部图的一个推广，是指一类满足以下性质的二部图：存在以$A$为顶点的共享1个端点的3条路形成的树$G'=(A,E')$，使得$B$中任意顶点的邻居在$G'$中连通. Jiang等人^[78]给出了一个算法求解三元凸二部图上的FVS，其运行时间为

该算法的思想是考虑唯一一个度数超过2的顶点，通过枚举此顶点是否在解中，从而将此问题转化为一般的凸二部图上的FVS求解. 另一方面，文献[79]还证明了星凸二部图（star convex bipartite graph）上的FVS是NP难的. 星凸二部图是指一类满足以下性质的二部图：存在以$A$为顶点的星图${G}'={K}_{1,\left|A\right|-1}$，使得$B$中任意顶点的邻居在$G'$中连通.

弦凸二部图（chordal convex bipartite graph），或简称弦二部图（chordal bipartite graph），也指不包含长度为$6$的导出环的二部图. Kloks等人^[80]证明了弦二部图上的FVS可以在$O\left({n}^{5}\right)$时间内解决. 树凸二部图（tree convex bipartite graph）是指一类满足以下性质的二部图：存在以$A$为顶点的树$G'=(A,E')$，使得$B$中任意顶点的邻居在$G'$中连通. 显然树凸二部图包含了凸二部图、三元凸二部图和星凸二部图. Jiang等人^[81]证明了树凸二部图一定属于弦凸二部图，并且证明了$3$度树凸二部图（即树凸二部图$G$所对应的树$G'$最大度不超过3）上的FVS问题是NP难的.

环凸二部图（circle convex bipartite graph），简称环二部图（circle bipartite graph），是指一类满足以下性质的二部图：存在以$A$为顶点的环$G'=(A,E')$，使得$B$中任意顶点的邻居在$G'$中连通. Liu等人^[82]给出了求解环二部图上FVS的多项式时间算法. 该算法首先计算4种类型的最大导出森林实现了对环二部图上反馈点集的计算. 此算法时间复杂度为

表9给出了二部图图类上反馈集问题和子集反馈集问题的计算复杂性.

表  9  二部图图类上反馈集和子集反馈集问题的计算复杂性

Table  9.  Complexity of Feedback Set and Subset Feedback Set Problems in Bipartite Graph Classes

问题	图类	计算复杂性
FVS/DFVS	二部图	NP难
FVS	路凸二部图	$O\left({n}^{2}m\right)$[62]
FVS	3度树凸二部图	NP难[81]
FVS	星凸二部图	NP难[79]
FVS	弦凸二部图	$O\left({n}^{5}\right)$[80]
FVS	环凸二部图	$O\left({n}^{4}m\right)$[82]
SFVS	补二部图	$O\left({n}^{4}\right)$[64]

下载: 导出CSV 

| 显示表格

4.   结束语

反馈集问题无论在实践中还是在理论上，都是十分重要的NP难问题. 从20世纪中叶至今，反馈集问题的高效算法设计及其计算复杂性一直都是研究的热门课题. 子集反馈集问题作为反馈集问题的一般化形式，自2000年起也得到了广泛关注和研究. 近十年，随着参数算法、近似算法等各类算法技术的革新，反馈集问题和子集反馈集问题出现了一些突破性的成果，使之成为了热门研究问题. 此外，不同特殊图类上的反馈集问题以及子集反馈集问题的复杂性都有较多的研究结果. 通过对反馈集与子集反馈集问题相关的复杂性和算法分析，目前主流的研究趋势可以从3个角度进行概括.

1）一般图上的反馈集问题与子集反馈集问题

在无向图上的反馈点集问题FVS的快速算法研究比较丰富，但其求解算法的时间复杂度仍然过大. FVS的以解集大小$k$为参数的参数算法（算法时间复杂度的指数部分仅与$k$相关）长期以来被多次改进，目前已知最快的确定性算法^[21]运行时间为${3.46}^{k}{n}^{O\left(1\right)}$，而最快的概率算法^[23]的时间复杂度为${2.7}^{k}{n}^{O\left(1\right)}$，突破了${3}^{k}$的瓶颈. FVS的确定性算法是否也能突破此瓶颈是许多学者关心的研究课题. 有向图上反馈集问题的难度更大，是否存在单指数运行时间的算法求解DFVS是一个长期公开性的难题. 此外，目前已知的非平凡精确算法仅有一个运行时间为$O\left({1.997\; 7}^{n}\right)$的算法^[26]，且此算法较为复杂，是否存在更快或者更简洁的精确算法还未知.针对求解DSFVS的参数算法，目前最快算法^[20]的时间复杂度高达${2}^{O\left({k}^{3}\right)}{n}^{O\left(1\right)}$. 是否存在单指数时间的参数算法在参数算法领域成为一个知名的公开问题.

2）特殊图上反馈集问题的计算复杂性

特殊图上的反馈集计算复杂性还存在一些细化工作尚未完成. 已知FVS在某些图类上是多项式可计算的，而在更大的图类上是NP难的，那么在介于两者之间的一些重要图类上，FVS是否为NP难是值得探索和研究的.

例如，目前已知在${P}_{4}$-free图以及弦图上的FVS是多项式可求解的^[58,65]，弱弦图（weakly chordal graph）是包含了这2类图的一个图类. 同时，完美图（perfect graph）上的FVS是NP难的^[39,62,79]，而弱弦图是完美图的一个子类. 目前未知FVS在弱弦图上是否是NP难的.

对于有单个禁止子图的禁止图上的FVS，其计算复杂性的分类工作仍在持续研究中. 对任意正整数$s\ge 0$，$(s+1){P}_{3}$-free图和$(s{P}_{1}+{P}_{5})$-free图上的FVS均可在多项式时间内求解^[73-76]. 然而，当禁止子图$H$是${P}_{6}$或$s{P}_{2}+{P}_{4}$的超集时，$H$-free图上的FVS是否是NP难的仍然未知.

3）特殊图上子集反馈集问题的计算复杂性

特殊图上子集反馈集问题的复杂性的结果相对较少. 例如，补比较图和区间图上的FVS存在高效的算法^[62,66]，那么补比较图上或区间图上的SFVS是否存在高效的算法尚未可知. 此外，对于有单个禁止子图的禁止图上的SFVS，其计算复杂性分类工作已基本完成^[77]. 有多个禁止子图的禁止图上的SFVS的计算复杂性工作仍然是值得进一步研究的课题.

作者贡献声明：白天提出论文总框架，负责文献及数据整理、图表绘制、定理证明，完成了该文撰写和修改；肖鸣宇对论文逻辑架构提出指导意见，参与部分重要内容的组织、初稿的审阅与修改.