Computational Complexity of Feedback Set and Subset Feedback Set Problems: A Survey
-
摘要:
反馈集问题（feedback set problem）是计算机科学中研究最为广泛和深入的图上NP完全问题之一，其在并发计算、大规模集成电路、编码设计、软件验证、社交网络分析等领域均存在重要的应用. 子集反馈集问题（subset feedback set problem）是反馈集问题的一种更一般化的形式，更加具有普适性和实用性. 近年来，这2个问题在计算复杂性上的分类工作已逐步完善，在算法领域也已出现许多重要的突破. 相关研究工作分为2个部分进行介绍. 第1部分详尽地介绍了反馈集和子集反馈集各种不同版本的问题，梳理了它们之间的一些重要关系，并介绍了这些问题在一般图上的计算复杂性. 第2部分系统性地介绍了反馈集和子集反馈集问题在一些重要子图类上的计算复杂性，包括度有界的图类、平面图类、竞赛图图类、相交图类、禁止图图类和二部图图类. 最后对反馈集和子集反馈集问题的研究现状进行分析和总结，概括了目前主流的研究趋势.
Abstract:The feedback set problem is one of the most widely and deeply studied NP-complete graph problems in the field of computer science, with important applications in concurrent computing, large-scale integrated circuits, coding design, software verification, and social network analysis. The subset feedback set problem is a nature generalization of the feedback set problem, and has much universal and practical. In recent several years, the classification of the computational complexity for these two problems has drawn certain interests, and many breakthroughs have been made in the area of algorithms. In this paper, the survey on these problems mainly contains two parts. The first part introduces different versions of the feedback set and subset feedback set problems. The essential relations among these versions and their computational complexity in general graphs are also discussed in this part. The second part introduces the computational complexity of the feedback set and subset feedback set problems in some important and classical graph subclasses, including degree bounded graphs, planar graphs, tournaments, intersection graphs, forbidden graphs, and bipartite graphs. Finally, by analyzing and summarizing the existing research, the major research trends on the feedback set and subset feedback set problems are outlined.
-
异常检测作为计算机领域中的一项关键任务，在现实世界中有着广泛的应用（时序异常[1-2]、网络异常[3-4]、航道异物[5-6]和安全监控[7]等）. 视觉领域中异常检测的目标是识别出正常样本中的异常样本，又分为对图像整体进行异常检测以及对图像中的物体进行异常检测和定位. 在现实场景中，由于视觉数据固有的复杂性（光照变化和像素级噪点等）和潜在干扰的多样性（遮挡、形变、异物干扰等），异常检测模型需要同时兼顾良好的泛化性和较高的准确率，因此这项研究具有较高的挑战性. 良好的异常检测模型可以应用于工业生产[8-12]、医疗诊断[13-15]和视频监控[16]等诸多领域，替代人工进行异常情况的检测和判断，极大提高工作效率，具有重要的现实意义.
传统异常检测研究可以分为基于分类、聚类、最近邻、统计信息和信息熵方法[17-18]等，而最近的基于深度学习的异常检测方法大多是在基于分类的方法上进行拓展，同时融合聚类、最近邻等机器学习方法，大致可以分为基于预训练模型和基于深度生成模型这2种思路. 基于预训练模型的方法[19-24]在大数据集（如ImageNet）[25]上训练出较好的特征提取器，再对异常样本和正常样本的特征进行处理，进一步扩大异常样本和正常样本的特征差异，从而实现异常检测；基于深度生成模型的研究使用自编码器（autoencoder，AE）或者生成对抗网络（generate adversarial network，GAN），经过编解码器将异常区域重构为正常区域[26-32]，通过分割结果进行异常检测.
上述2类方法均是通过学习正常样本和异常样本的特征差异实现异常检测. 然而现实场景中图像的异常区域往往较小，导致正常样本和异常样本的特征差异较小. 同时由于场景较为复杂，通过模型提取到的图像特征存在较大分布差异. 因此无论是基于预训练模型还是基于深度生成模型的方法，在面对复杂多变的真实场景时，均难以保持较高的异常检测性能.
基于此，本文受Yuan等人[33]提出的合成场景中无限制遮挡物体的生成建模（generative modeling of infinite occluded objects，GMIOO）方法的启发，提出如下假设：图像是由正常的背景区域和可能存在异常的前景区域2部分组成的. 基于上述假设，本文提出了基于背景-前景组成式建模的异常检测方法（anomaly detection based on background-foreground compositional modeling，AD-BFCM），将图像划分为背景区域和前景区域，分别进行背景建模和前景建模. 在背景建模阶段，模型对输入图像进行编解码，将图片可能存在异常的区域重构为正常区域，得到干净的重构背景图像. 针对图片中可能存在的各种干扰，模型通过跳层连接和对异常区域的额外约束，让模型在重构背景的同时保留干扰信息，降低模型的异常检测误识别；在前景建模阶段，模型针对图像的异常区域进行编解码，通过以物体为中心的方法[34]学习到多个异常物体的外观、形状、位置和存在表示，再通过组成建模的方式重构出整张图像，并对异常物体的存在表示设定阈值来实现对图像中异常物体的检测和定位.
在数据集方面，现有的工业异常检测数据集如MVTec[8]，VisA[35]等主要关注物体表面的异常纹理，而实际工业生产往往关注场景中是否存在异常物体，大部分公开数据集难以满足这一需求. 同时，由于生产工序和成本等问题，工业场景中的图片需要集中采集，数据本身存在一定的同质化. 基于此，本文模拟工业生产中采集数据同质化情况，从来自工业生产的9个电路板场景图片中抽取少量数据，配合一种简单的数据合成方法构建出相当数量的合成数据集用以训练. 同时剩余图片作为测试集来验证模型是否在全部真实场景中拥有较高的异常检测性能. 此外，本文还在航道异物碎片 （foreign object debris in airports，FOD-A）数据集[36]上进行方法验证. 该数据集包含机场跑道上可能存在的异物碎片图片. 实验结果表明本文在FOD-A数据集上的漏检率仅为2.89%，在自建的电路板异物（foreign object in circuit board，FO-CB）数据集上漏检率达到0%，检测出9个电路板场景中的全部异常物体.
本文的主要贡献包括3个方面：
1） 针对实际工业生产中异常检测的需求，利用工业生产中真实电路板图片，构建了FO-CB数据集. 该数据集模拟工业生产中采集数据同质化的情况，利用少量数据配合数据合成方法得到训练集，剩余真实数据作为测试集.
2） 假设图像可划分为背景区域和前景区域，提出了一种基于背景-前景组成式建模的异常检测方法，用以检测复杂真实场景中的异常物体. 模型分为背景建模阶段和前景建模阶段. 在背景建模阶段，模型通过特征提取器重构出不包含异常物体的干净背景；在前景建模阶段，模型通过自编码器学习异常物体的表示，实现异常物体检测.
3） 在背景建模阶段，模型增加了跳层连接的设计和约束重构区域的损失函数，实现重构背景的同时保留干扰信息. 在前景建模阶段，模型设计了针对局部前景的重构损失函数，来更好地学习异常前景表示.
1. 相关工作
1.1 异常检测研究
传统的异常检测方法大多基于统计学的方法，利用距离、分布等统计信息，对正常样本和异常样本进行聚类或最近邻分析，来实现对异常样本或视频中异常物体的识别[11-12]. 例如文献[37–38]基于已训练的分类器，通过计算正常样本和异常样本的分布差异，实现对图像和视频的异常检测.
基于深度学习方法的异常检测大致可以分为2个范式，即基于深度学习预训练模型的方法和基于生成模型的方法. 基于深度学习预训练模型的方法[19-24]大多通过大规模数据集训练得到特征提取器，再对异常样本特征和正常样本特征进行处理，实现异常检测. Defard等人[20]利用预训练的卷积神经网络（convolutional neural network，CNN）进行Patch嵌入，并通过多变量高斯分布得到正常类的概率表示，实现单类环境下异常检测和定位. Roth等人[21]构建了一个补丁级特征库，通过判断图像中是否存在异常补丁来实现像素级异常检测. Gudovskiy等人[23]通过多尺度金字塔结构获得全局和局部语义信息，通过条件归一化流网络进行异常检测. 除了对特征进行后处理，文献[39–41]对预训练模型进行知识蒸馏，通过比较教师网络和学生网络之间的异常区域特征的差异来估计异常. 此外，Li等人[24]利用数据增强策略，将图像补丁切割并粘贴在图像随机位置，通过自监督方式学习异常表征.
基于生成模型的方法通常使用编码器将输入图像压缩成低维表示，再通过采样方式得到数据的分布，经过解码器重构输入图像，以此学习到正常数据和异常数据的特征分布差异. Dehaene等人[42]基于变分自编码器（variational autoencoder，VAE）模型，使用梯度下降法对自动编码器损失的能量函数进行投影，将样本投影到自动编码器正在学习的数据流上，迭代重构出正常样本. Baur等人[13]使用自编码器对正常的大脑MR图像进行建模，并通过比较与正常分布的偏差进行异常检测. Dehaene等人[28]利用变分自编码器对正常样本进行不同特征维度的重建，通过和正常样本的偏差检测异常. Hou等人[30]同样通过变分自编码器对正常样本进行建模，同时构建了多尺度记忆模块来储存不同分辨率的特征，并引入对抗学习来提升异常检测性能. 此外，还有一些基于GAN的生成模型工作[26-27,43]，这些工作将输入图像与生成网络中生成的正常图像进行比较，通过判别网络来评估是否存在异常.
基于深度学习预训练模型的方法更加依赖于训练集的数据分布，在测试数据分布和训练数据分布差别较大时，模型难以维持稳定的高性能. 基于生成模型的方法通过学习正常样本和异常样本的重构差异来进行异常检测，面对开放场景中的未知干扰时，往往会重构错误，从而导致误检测的情况.
1.2 以物体为中心的表征学习
以物体为中心表征学习方法的核心思想是：视觉场景图像可以被建模为多个物体的组成，通过学习视觉场景中出现的每个物体的表征，可以得到整个视觉场景的表征. 现有的以物体为中心的表征学习方法大多使用空间混合模型或加权求和方法对视觉场景建模[42-46]. 文献[44–45]使用注意力机制依次提取图像中每个物体的表征. 文献[33]首先学习场景图像的表征，然后依次学习每个物体的表征，并进行迭代更新. 文献[46–47]利用卷积神经网络生成候选物体，在包含大量物体的场景中有较好表现. 文献[34, 48]初始化所有物体的表征，然后通过竞争机制进行表征的迭代更新. 文献[49–50]将视觉场景中的结构信息结合到深度生成模型，以便生成更多的连续性样本. 文献[51]首先从单个对象的场景图像中获取知识，然后在新的多对象场景图像中学习物体表征. 这些方法通过不同的方法分离出物体，通过以物体为中心的表征学习机制，学习图像中的物体表征.
上述相关工作[33-34,42-48]可以看出，以物体为中心的表征学习方法将图像视为多个物体的组成，而工业生产中的异常检测场景亦可视作正常背景和可能存在的异常物体的组成，与以物体为中心的表征学习方法存在共通性. 因此，本文方法引入以物体为中心的表征学习方法，对图片分别进行背景和异常前景的建模.
2. 模拟工业生产环境的合成数据集
本节主要描述工业生产中异常检测面临的数据问题、构成合成数据集的方法和期望解决的问题.
2.1 工业生产中的异常检测问题
工业生产中存在大量流水线装配场景，在自动化装配过程会出现零件掉落的情况，因此需要及时清理以免造成更大损失. 然而现有异常检测数据集大多聚焦于工业生产中单个零件或场景的缺陷问题，缺乏针对装配场景的异常物体检测数据集.
除此之外，考虑到生产线上的流水化运作和高昂的停机成本等问题，工业生产中的数据采集往往会集中在同一时间段内，这导致数据本身（训练集）存在一定的同质化. 而实际工业场景（测试集）囊括了光照变化、遮挡形变和动态干扰等诸多因素，相较于采集的数据（训练集）更加开放.
因此，本文基于工业生产中的真实电路板数据，从9个场景共
5507 张图片中抽取少量不包含异常物体的正常背景图片，配合17个异常物体图片，通过数据合成的方式得到存在数据同质化的训练集. 剩余真实电路板数据归为测试集.2.2 数据集合成
图1详细展示了数据集合成的过程，具体可以分为2个步骤：步骤1从真实数据集中随机抽取图片；步骤2基于步骤1中抽取的图片，将17个异常物体和抽取的图片按照规则进行图片合成. 图1中最左侧的代表图像展示9种不同真实电路板场景：序号为1，2，3，4的场景包含常见的电子元件和敷铜板，同时囊括了电路板场景中常见的反光问题；序号5，6的场景包含长宽比较大的电子元件；序号7，8的场景包含长宽较小的电子元件，同时囊括了墨点等干扰问题；序号9的场景包含多种电路板原件，反映了真实场景的复杂性.
首先，本文提出真实场景图片抽取算法，如算法1所示. 算法1读取9个真实场景共
5507 张图片，依据类别信息从每个场景中随机选取6~10张不包含异常前景物体的图片.算法1. 真实场景图片抽取算法.
输入：9类场景中不包含异常物体的真实图片集合NormalImages和每类场景随机抽取图片数量集合Num；
输出：随机抽取场景图片的集合SampleImages.
Fuction RandomSample
① dictnimage ←NormalImages；
② dictnumber ←Num；
③ dictsample←{}；
④ for class，images∈enumerate (dictnimage) do
⑤ n = dictnumber[class] ；
⑥ samples= fsample (images, n)；
⑦ dictsample[class] ←samples；
⑧ end for
⑨ SampleImages←dictsample；
⑩ return SampleImages.
基于算法1返回的结果，结合已标注的17个异常前景物体，本文提出电路板数据集合成算法，如算法2所示. 算法2通过合成数据的方式将算法1中随机抽取的图片和已标注的异常前景物体随机组合，生成训练集和验证集. 未被算法1抽取的剩余图片全部作为测试集图片. 具体的合成规则有5条.
1）存在异常比例. 工业生产中正常样本数量通常远远大于异常样本数量. 基于此，在构建合成数据集的过程中，将图片中可能存在异常的比例调整为20%，即平均每10张图片里有2张存在异常.
2）前景旋转. 由于真实场景中提供的标记数据数量有限，为了更好地让模型学习异常物体的表征信息，本文方法对异常前景物体进行了数据增强，将17个异常前景样本随机旋转0°，90°，180°，270°，然后进行数据合成.
3）前景缩放. 不同场景中的异常物体存在尺度变化，本文方法通过对异常前景物体进行尺度缩放来模拟这一变化，将尺度缩放范围设置为0.75~1，随机缩放异常前景物体.
4）前景数量. 实际场景中，异常物体可能存在复数情况，本文数据集考虑真实场景中异常物体的实际数量，将前景数量设置为0~2，以此模拟真实环境中的电路板装配.
5）其他设置. 本文方法将训练集和验证集设置为同等数量，让模型更好地学习物体表征；同时本文方法将合成数据集扩充倍数设置为500，以产生足量数据训练模型.
基于上述合成规则，本文利用算法2合成电路板数据集，具体如下所示.
算法2. 电路板数据集合成算法.
输入：包含9类场景的真实图片集合Images，随机抽取的电路板场景图片集合SampleImages，异常前景物体集合ObjectImages，对应的异常前景图片掩码集合MaskImages，前景旋转集合Rot={π/2, π, 3π/2, 2π}, 前景缩放集合Scal={0.75, 1}，前景数量上限Objmax=2，训练集验证集划分比例line=0.5，合成数据扩充比例expand=500；
输出：训练集Train，验证集Valid和测试集Test.
函数：RotObj实现对异常前景物体随机旋转；AddObj将异常前景物体合成到图像中的随机位置.
Fuction CreateDataset
① dictsample ←SampleImages；
② dicto ←ObjectImages；
③ dictm ←MaskImages；
④ Train，Valid，Test ←{}；
⑤ for id，image∈enumerate (dictsample) do
⑥ iftrain = Random (line)；
⑦ for i ∈range (expand) do
⑧ objnum = Random (0, Objmax)；
⑨ im = dictsample[id]；
⑩ imm = Initial (image)；
⑪ for j ∈range (objnum) do
⑫ objid, obj = fsample (dicto)；
⑬ objm = dictm[objid]；
⑭ obj, objm = RotObj (obj, objm, Rot）；
⑮ im, imm = AddObj (im, imm, obj, objm, Scal)；
⑯ end for
⑰ if iftrain > line do
⑱ Train[id, i]←{im, imm}；
⑲ else do
⑳ Valid[id, i]←{im, imm}；
㉑ end if
㉒ end for
㉓ end for
㉔ Test←Images\ (Images ∩ SampleImages)；
㉕ return Train，Valid，Test.
值得注意的是，在现实场景中，测试集作为开放集，存在大量模型从未见过的场景图片，对模型的泛化性有较高要求. 因此，本文将训练集和验证集中的场景图片设置为互斥，让模型在训练阶段尽可能基于输入图像本身进行重构，从而在面对未知图像时仍能够重构出图像中的细节信息.
上述合成规则存在可拓展性，当数据集或对应任务发生变化时，可以通过调整合成规则来快速适应新的任务或模拟新的实际场景，辅助更多研究应用和落地.
3. 基于组成式场景建模的异常检测方法
本节首先简介GIMOO[33]方法，然后详细描述本文所提方法的算法细节，具体分为背景建模阶段和前景建模阶段，同时简述整体算法的代码流程和生成过程.
3.1 GMIOO模型
GMIOO模型作为深度生成模型，在无监督场景下学习输入图像中多个物体的潜在表示，解耦物体的位置、形状和外观等属性，并实现对多个物体的重组和对整张图片的组成式建模. GMIOO模型首先将图像输入背景编解码器，得到背景的隐空间表示；然后将输入图像和背景隐空间表示输入前景编码器，获得前景对象的隐空间表示，并以此推断多个前景物体存在的重叠遮挡；最后通过前景解码器重构出多个前景物体并和背景进行组合，实现无监督下对整张图片的组成式重构.
3.2 基于背景-前景组成式建模的异常检测方法
本文受到GMIOO的启发，提出了如下假设：异常检测场景的图片由正常的背景区域和可能存在异常的前景区域组成. 基于上述假设，本文提出了一种基于背景-前景组成式建模的深度学习框架，如图2所示. 该框架包含背景建模阶段和前景建模阶段.
在背景建模阶段，模型将可能的异常前景视为“噪声”，通过多层卷积网络得到图像的低维表示，并通过上采样播值和全连接层重构出不含“噪声”的干净背景图片. 在该阶段，模型将原图-背景对作为输入，利用跳层连接等操作尽可能保留原图中背景的复杂纹理特征，让模型具备重构真实背景的能力.
在前景建模阶段，模型将重构背景和原始图像作为输入，利用编码器将图像编码为潜在变量表示，通过对潜在变量进行采样来学习图像中异常物体的外观、形状和存在表示，并结合重构背景，通过组成式建模得到完整重构图像. 该阶段模型借鉴了生成模型的思路，在缺乏监督的情况下使用自编码器学习异常物体的表示，这让模型能够更有效地应对真实场景中多变的异常物体，具备良好的异常检测能力.
3.3 背景建模阶段
在该阶段，模型由背景编码器（background encoder，BGE）、背景解码器（background decoder，BGD）和跳层连接构成. 输入图片x经过背景编解码器，得到不包含异常前景的干净背景ˆxbck.
3.3.1 背景编码器
为了对输入图像x进行编码，背景编码器利用多层卷积对样本进行变换，其中包括2D卷积层（convolution layer，Conv2d）、下采样插值（down interpolate）和非线性激活层ReLU（rectified layer units）组成，具体如下：
zbck=fbckenc(x), (1) 其中x为输入样本，zbck为经过背景编码器得到背景潜在表示，fbckenc(⋅)为采用多层卷积的背景编码器.
3.3.2 背景解码器
得到背景潜在表示zbck后，通过背景解码器可以重构出不包含异常物体的背景图片ˆxbck. 背景解码器采用多层卷积、上采样插值、ReLU和跳层连接，将背景隐变量zbck恢复到输入图像尺寸，输出重构图像˜x和局部重构区域˜xmask，具体如下所示：
˜x,˜xmask=fbckdec(zbck)， (2) 其中fbckdec(⋅)为包含卷积层、上采样插值、ReLU和跳层连接的背景解码器. 值得注意的是，由于模型面向真实场景任务，单纯对背景隐变量解码难以重构出精确的背景图像. 受到U-net[52]的启发，本文在背景编码器和背景解码器之间增加了跳层连接，来传递图像不同尺度下的纹理特征，让模型能够应对真实场景中的背景建模任务.
获得重构表示˜x和重构区域˜xmask后，通过线性计算可得到不包含异常前景的干净重构背景ˆxbck，具体为：
ˆxbck=˜xטxmask+x×(1−˜xmask). (3) 3.3.3 背景建模损失函数
模型通过重构方法得到干净背景ˆxbck，而真实场景中图像普遍存在遮挡、噪声、反光和形变等动态干扰，这会导致模型重构的区域˜xmask逐渐扩大，而较大的重构区域会导致模型在前景建模阶段更加难以学习异常前景表示. 基于此，本文在背景重构的基础上，增加了对重构区域的约束，让模型在有限区域内完成重构. 具体的目标损失函数为：
LBGD=Lbck+αbckLarea, (4) Lbck=‖ (5) {L_{\rm area}} = \arg \min \left( {{S^{\rm bck}}} \right), (6) 其中{S^{\rm bck}}为重构区域{\tilde x^{\rm mask}}的激活区域，{\alpha _{\rm bck}}为给定的超参数. 可以看出，Larea通过约束重构区域{\tilde x^{\rm mask}}的激活面积，让模型集中重构可能存在异常背景区域. Lbck通过计算输入图像x和重构背景{\hat x^{\rm bck}}的均方误差实现对整体图像的重构约束. Larea和Lbck的组合让模型在拥有较好重构效果的同时，对存在干扰的真实场景有良好的泛化性能.
3.4 前景建模阶段
在前景建模阶段，模型借鉴GMIOO模型中的前景编解码器，由3部分组成：全景图像编码器（full image encoder，FIE）、空间变换网络（spatial transformer network，STN）和局部自编码器（local autoencoder，LAE）. 输入图像x和重构背景{\hat x^{\rm bck}}首先经过全景图像编解码器和空间变换网络，得到异常物体的位置信息，然后输入局部自编码器得到异常物体的外观、形状和存在表示. 上述操作将迭代K次（K为超参数，代表图像中可能存在异常物体的最大数目），每次得到的异常物体表示将在下一次迭代中输入全景图像编码器. 在经过K次迭代后，模型通过组成式建模的方式得到最终的重构图像\hat x.
3.4.1 全景图像编码器
全景图像编码器由多层卷积网络和长短期记忆网络组成. 首先将输入图像x、重构背景{\hat x^{\rm bck}}、初始掩码{\tilde x^{\rm mask}}和先前得到的异常物体表示进行concatenate操作，然后输入FIE得到第k次迭代的异常前景空间变换表示z_k^{\rm stn}，具体如下：
z_k^{\rm stn} = {f_{\rm FIE}}\left( {x,{{\hat x}^{\rm bck}},{{\tilde x}^{\rm mask}},\hat x_{1:k - 1}^{\rm obj}} \right). (7) 当k=1时，FIE的输入仅包括图像x、重构背景{\hat x^{\rm bck}}和初始掩码{\tilde x^{\rm mask}}.
3.4.2 空间变换网络
得到z_k^{\rm stn}后，输入STN网络可以得到可能存在的异常前景物体的空间变换和对应的局部图像，具体为：
x_k^{\rm crop} = {f_{\rm STN}}\left( {x,z_k^{\rm stn}} \right), (8) 其中k表示异常物体的序号，x_k^{\rm crop}表示经过空间变换的局部图像.
3.4.3 局部自编码器
局部自编码器包含局部编码器（local object encoder，LOE）和局部解码器（local object decoder，LOD）这2部分. LOE由多层卷积和长短期记忆网络组成，经过STN的局部图像x_k^{\rm crop}经过编码器后，得到异常物体外观、形状和存在的隐空间表示：
z_k^{\rm apc},z_k^{\rm shp},z_k^{\rm pre} = {f_{\rm LOE}}\left( {x_k^{\rm crop}} \right) . (9) LOD由多层反卷积网络和长短期记忆网络组成. 将异常物体的隐空间表示输入解码器，可以得到异常物体的外观、形状和存在的重构表示：
\hat x_k^{\rm apc},\hat x_k^{\rm shp},\hat x_k^{\rm pre} = {f_{\rm LOD}}\left( z_k^{\rm apc},z_k^{\rm shp},z_k^{\rm pre},z'^{\rm stn}_k \right), (10) 其中 z'^{\rm stn}_{1:k} 为z_{1:k}^{\rm stn}的逆变换. 经过计算可以得到序号为k的重构异常物体：
\hat x_k^{\rm obj} = \hat x_k^{\rm apc} \times \hat x_k^{\rm shp} \times \hat x_k^{\rm pre} . (11) 上述迭代过程持续K次后，可以得到所有异常物体的重构表示，结合背景建模阶段的重构背景，可以得到最终的重构图像 \hat x ，具体为：
\hat x = {\hat x^{\rm bck}} \times \left( {1 - \sum\limits_{k = 1}^K {\hat x_k^{\rm pre}\hat x_k^{\rm shp}} } \right) + \sum\limits_{k = 1}^K {\hat x_k^{\rm obj}} . (12) 3.4.4 前景建模损失函数
通常来说，基于生成方法的损失函数只计算整张图片的重构损失，而本文模型采取背景-前景组成式建模的方式，单独对背景进行建模，在前景建模阶段已经得到较好的重构背景表示. 为了让模型更好地学习前景物体的表示，本文在整体图像损失的基础上增加了针对异常物体的局部损失函数，具体为：
{L_{\rm recon}} = {L_{\rm image}} + {\alpha _{\rm local}}{L_{\rm local}} , (13) {L_{\rm image}} = \left\| {x,\hat x} \right\|_2^2 , (14) L_{\rm{l}ocal}=\sum\limits_{k=1}^K \left\| x_{1:k}^{\rm{c}rop},\hat{x}_{1:k}^{\rm{o}bj} \right\| _2^2， (15) 其中 {\alpha _{\rm local}} 为给定的超参数， {L_{\rm recon}} 由 {L_{\rm image}} 和 {L_{\rm local}} 组成. {L_{\rm local}} 直接对异常物体进行约束，让模型对可能存在的异常物体重构更加准确. {L_{\rm image}} 聚焦整体图像的重构，保证多个异常物体和重构背景组合而成的完整图像更加贴近输入图像. 改进后的损失函数 {L_{\rm recon}} 使得模型前景物体和背景图像均有较好的重构效果.
3.5 算法流程
本节详细展示了本文模型的算法流程，具体分为背景建模和前景建模2个阶段. 算法3展示了2个阶段的伪代码，并详细展示了前景建模阶段中针对前景物体的K轮迭代过程.
算法3. 基于背景-前景组成式建模的异常检测算法.
输入：输入图像x；
输出：重构图像\hat x和异常检测结果 x_{1:K}^{\rm pre} .
① for i ∈ range（epoch）do /*背景建模阶段训练， epoch为背景建模阶段的训练轮数*/
② zbck = fBGE (x)；
③ {\hat x^{\rm bck}}= fBGD (zbck)；
④ end for
⑤ for i ∈ range（epoch）do /*前景建模阶段训练， epoch为前景建模阶段的训练轮数*/
⑥ for k ∈ range（K）do /*K次迭代过程*/
⑦ if k == 0
⑧ zimage = fFIE（x,{\hat x^{\rm bck}},{\tilde x^{\rm mask}},{\hat x^{\rm obj}}）；
⑨ else
⑩ zimage = fFIE（x,{\hat x^{\rm bck}},{\tilde x^{\rm mask}}）；
⑪ end if
⑫ x_k^{\rm crop} ,z_k^{\rm stn} =f_{\rm STN}(x,z^{\rm image}) ；
⑬ z_k^{\rm apc} , z_k^{\rm shp} , z_k^{\rm pre} = f_{\rm LOE}(x_k^{\rm crop})；
⑭ x_k^{\rm apc} , x_k^{\rm shp} , x_k^{\rm pre} = f_{\rm LOD}(z_k^{\rm apc}, z_k^{\rm shp}, z_k^{\rm pre})；
⑮ end for
⑯ \hat x ={\hat x^{\rm bck}} \times (1–sum(x_k^{\rm shp} +))+sum(x_k^{\rm apc} \times x_k^{\rm shp} \times x_k^{\rm pre}) ；
⑰ end for
⑱ return \hat{x} ， x_{1:K}^{\rm pre} .
4. 实验与评估
4.1 实验环境和数据集
1）实验环境. 本实验基于Ubuntu环境，使用Python语言，在Linux环境下进行模型搭建. 平台主要硬件参数为：CPU使用Intel Xeon E5-2603，16 GB 内存，GPU使用NVIDIA GTX 1080 Ti，11 GB显存.
2）数据集. 本文分别在公开数据集FOD-A和自建数据集FO-CB上进行实验. 公开数据集FOD-A由机场跑道常见的异物碎片图片组成，共计31个类别，超过
30000 张标注图片，囊括了不同的光照和天气类别. 自建数据集FO-CB由工业生产中的真实电路板装配图片组成，共计9个场景5507 张图片，囊括了电路板装配厂景中各种电子元件，如表1所示. 其中训练集和验证集（共186张）由少量真实场景和异常物体（螺丝钉）通过简单数据合成方式得到，测试集由剩余电路板装配图片（共5321 张）构成.表 1 FO-CB数据集信息Table 1. FO-CB Dataset Information数据集 场景数量 真实图像 （合成）图像总数 异常数据比例 训练集 9 92 46000 0.20 验证集 9 94 47000 0.20 测试集 9 5321 5321 0.02 4.2 评估方法
异常检测通常采用深度学习领域通用的混淆矩阵来衡量模型的性能. 该矩阵描述样本的实际类别并预测类别的混合，分为真阳性（true positive，TP）、假阳性（false positive，FP）、假阴性（false negative，FN）和真阴性（true negative，TN）. 具体如表2所示.
表 2 混淆矩阵Table 2. Confusion Matrix实际类别 检测正常 检测异常 正常类 TP FN 异常类 FP TN 本文采用实际生产中更为关注的异常元件漏检率（miss rate，MR）和异常原件误检率（incorrect rate，IR）.
1）漏检率. 表示检测为正常样本的异常样本在实际异常样本中所占的比例. 计算方法为：
MR = \frac{{FP}}{{FP + TN}} \times 100\% . (16) 2）误检率. 表示错误归类的样本在总体样本中的比例. 计算方法为：
IR = \frac{{FP + FN}}{{TP + FP + TN + FN}} \times 100\% . (17) 4.3 实验参数
模型训练阶段分为背景建模阶段和前景建模阶段，各阶段对应的训练参数如表3所示. 其中迭代轮数表示模型在不同阶段训练的轮数；批数量表示每一次迭代输入网络的图片数量；K表示图像中可能存在的异常物体最大数量的超参数；{\alpha _{\rm bck}}和 {\alpha _{\rm local}} 分别为Larea和Llocal的超参数.
表 3 训练参数Table 3. Training Parameters训练参数 背景建模阶段 前景建模阶段 迭代轮数 10000 12000 批数量 128 128 K 2 2 {\alpha _{\rm bck}} 5 {\alpha _{\rm local}} 5 表4展示了模型在背景建模阶段的网络细节. 背景建模阶段包括BGE和BGD模块.
表 4 背景建模阶段网络Table 4. Network in Background Modeling Stage模块名称 结构细节 BGE 2D卷积+向下插值+激活函数（4层） BGD 2D卷积+向上插值+激活函数（4层）
4层跳层连接表5展示了模型前景建模阶段的网络细节. 前景建模阶段包括FIE，STN，LAE模块，其中STN直接调用torch的仿射变换，故而表5仅展示FIE和LAE这2个模块.
表 5 前景建模阶段网络Table 5. Foreground Modeling Stage Network模块名称 结构细节 FIE 长短期记忆网络+线性层+层归一化 LAE （LOE） 长短期记忆网络+线性层+层归一化 LAE（LOD） 2D卷积+向上插值（4层）
线性模块+层归一化（4层）4.4 对比方法
为了验证本文方法在不同阶段的有效性，本文在背景和前景建模阶段分别与不同的方法进行对比. 在背景建模阶段，本文方法选取U-net[52]和GMIOO[26]中的背景自编码器（GMIOO-AE）方法进行比较. 在前景建模阶段，本文方法选取2种基于深度学习的方法进行比较：1）DFKDE（deep feature kernel density estimation）[53]；2）PaDiM（patch distribution model）[14] .
1）U-net. U-net是一种用于图像分割的卷积神经网络模型. 该模型为编码-解码结构，在编码阶段逐层提取图像的特征，在解码阶段通过对称的结构来还原图像中的细节信息. U-net模型在训练样本较少的情况下同样能够准确进行图像分割.
2）GMIOO-AE. GMIOO是一种以物体为中心的组成式建模架构. 该架构包含背景建模和前景建模. GMIOO-AE表示该架构中进行背景建模的网络结构，由编码器和解码器组成. GMIOO-AE能够在无监督情况下完成对图像的背景重建.
3）DFKDE. DFKDE是一种快速异常分类算法，分为深度特征提取阶段以及由主成分分析（principal component analysis，PCA）和高斯核密度估计组成的异常分类阶段. 其中特征提取阶段由在ImageNet上预训练的ResNet-18[54]网络组成；异常分类阶段先将特征压缩为16个主成分，然后通过高斯核密度来评估图像是否存在异常.
4）PaDiM. PaDiM是一种基于深度神经网络的异常检测方法. 该方法利用预训练的卷积神经网络进行patch嵌入，通过多元高斯分布得到图像的概率表示. PaDiM适用于单类检测问题，并利用不同层次语义的相关性更好地定位图像中的异常.
本文将在实验部分与上述方法分别比较局部背景的重构效果和异常前景的检测结果，以此验证本文方法在不同阶段的实验效果.
4.5 实验结果
4.5.1 背景阶段重构结果
图3展示了背景建模阶段中模型在FO-CB测试集上的重构效果. 图3中输入图像表示原始图像，局部重构表示模型输出的重构结果. 通过重构结果可以看出，本文模型能够在每个场景仅使用少量的真实图像作为合成数据训练的情况下，准确建模真实场景中的图像背景. 这些结果同样证明了本文模型在背景建模阶段具备良好的鲁棒性和泛化性，对可能存在的未见过的图片仍然能够准确重构出不包含异常物体的背景图像.
鉴于现实世界场景中普遍存在照明和遮挡等干扰，模型在训练过程中存在通过扩大局部重构区域来应对潜在的异常物体的现象. 这会导致模型泛化性下降，面对从未见过的图像难以准确重构出干净背景. 为此，本文设计了Larea约束来调节局部重建区域的面积，迫使模型在尽可能小的区域内完成针对异常物体的重构. 这一改进不仅提升了模型的泛化性能，同时确保模型在面对从未见过的图像时，能够有效还原图像中可能存在的各种干扰，让重构的干净背景图像更加贴近原有图像. 表6表明在背景建模阶段添加Larea后，模型在验证集上的重构损失从13.97降低至5.66. 这说明Larea能够更好地辅助模型实现对于从未见过场景的背景重构.
表 6 Larea实验分析Table 6. Experiment Analysis of Larea模块 Larea 均方误差 BGM 无 13.97 有 5.66 为了验证本文方法的有效性，本文方法与U-net和GMIOO-AE这2种方法进行比较. 图4展示了3种方法的局部重构效果，可以看出U-net方法倾向于重构整张图像，局部重构较为模糊；GMIOO-AE方法由于缺乏损失函数的约束，重构区域相较于其他2种方法更加零散，同时重构效果较差；本文方法的局部重构图像较为清晰，同时重构区域包含异常物体（螺丝）的完整形状. 由此可见，本文方法在背景建模阶段中局部重构和约束重构区域的设计，使得模型在背景重构阶段取得了较好的效果.
4.5.2 前景阶段重构结果
图5展示了模型在FO-CB测试集上的异常检测结果，图5中框表示模型检测到存在异常物体的区域（有框表示结果正确）. 可以看出，模型在面对测试集中从未见过的真实场景，能够准确检测出图像是否存在异常并对异常物体进行定位. 当螺丝钉位于图像边缘或者复杂环境（数字区域或颜色相近的区域）时，模型仍然能够给出正确的定位. 这也说明模型具有较好的泛化性，能够在真实场景中完成异常物体的检测任务.
![]()
图 5 前景建模阶段异常检测结果注：图中矩形框表示检测正确.Figure 5. Anomaly detection result in the foreground modeling phase表7显示了AD-BFCM模型在9个不同场景下的异常检测结果. 可以看出，9个场景中的漏检率为0%，整体误检率为4.55%. 这说明模型在没有监督信息的情况下识别出了9个场景中所有的异常物体. 虽然模型整体误检率在4.86%，但对于工业生产环境中的异常检测任务，异常样本的漏检相对于正常样本的误检显得更为重要. 在保证漏检率为0%的情况下，4.86%的误检率是可以接受的. 此外，该模型在其中6个场景（具体序号为：3，4，5，6，7，8）中的误检率接近或低于整体误检率，说明模型能够在大多数场景中保持较低的误检率，仅在少部分场景具备较高误检率. 实验结果表明，该模型在不同的电路板装配场景中，能够检测出全部的异常物体，并在大多数场景中保持相对较低的误检率.
表 7 异常检测实验结果Table 7. Experiment Results of Anomaly Detection% 评估
指标场景
1场景
2场景
3场景
4场景
5场景
6场景
7场景
8场景
9合计 漏检率 0 0 0 0 0 0 0 0 0 0 误检率 9.6 8.5 4.7 2.5 1.5 3.2 3.1 0 6.9 4.86 为了验证本文方法在异常检测的效果，与DFKDE和PaDiM这2种方法分别在公开数据集FOD-A和自建数据集FO-CB上进行比较. 由于大多数异常检测方法在训练过程中需要较为充足的正常样本以学习正常样本和异常样本的差异，本文在训练DFKDE和PaDiM的过程中使用了80%的真实数据（
5507 张真实场景图片），并将剩余20%数据作为测试集.图6展示了3种方法在FO-CB数据集的异常检测结果，其中DFKDE和PaDiM展示图像级异常检测结果，本文方法展示图像级异常结果和定位结果. 由图6可以看出DFKDE和PaDiM方法对于图像中的异常物体都存在漏检情况，同时异常检测阈值接近50%. 本文方法能够检测出所有包含异常物体的真实图片，同时实现对异常物体较为准确的定位.
表8展示了AD-BFCM与DFKDE和PaDiM方法在数据集FOD-A和FO-CB上的异常检测性能. 实验结果表明，AD-BFCM模型不仅在自建数据集FO-CB漏检率达到0%，在公开数据集FOD-A上漏检率低至2.89%，优于其他2种对比方法.
表 8 FOD-A，FO-CB数据集漏检率对比Table 8. Comparison of MR in FOD-A and FO-CB Datasets% 模型 FO-CB数据集 FOD-A数据集 PaDiM 10.53 12.24 DFKDE 2.63 3.10 AD-BFCM 0.00 2.89 4.5.3 消融实验
为了验证本文方法中各个模块的有效性，本节从AD-BFCM模型中删除了部分功能，得到5种不同模型，并进行消融实验. 模型1~5的具体设置如下所示：
1）模型1. 未对图像的建模阶段进行区分，将模型的背景阶段模块和前景阶段模块合并训练，未使用图像-干净背景对进行训练.
2）模型2. 对图像的建模阶段进行划分，分别训练背景建模阶段和前景建模阶段，未使用图像-干净背景对进行训练背景建模模块.
3）模型3. 在模型2的基础上，使用图像-干净背景对训练背景建模模块，未使用Larea和Llocal对模型约束.
4）模型4. 在模型3的基础上增加Larea对背景建模进行约束，未使用Llocal对前景建模进行约束.
5）模型5. 代表最终模型，同时包含Larea和Llocal，对背景和前景同时进行约束.
实验结果如表9所示. 从结果可以看出，模型2相较于模型1漏检率和误检率分别下降3.71个百分点和12.38个百分点，说明分阶段图像建模能够小幅提升模型性能. 模型3在背景建模阶段增加图像-背景对进行训练，相较于模型2性能获得明显提升，漏检率和误检率分别下降8.74个百分点和21.07个百分点. 这说明真实场景中图像背景往往较为复杂，需要通过额外信息辅助模型重构背景. 模型3的误检率达到2.17%，优于其余模型，这是测试集大多为正常样本导致的，其漏检率高达9.09%也验证了这一点. 同时在工业生产中，相较于正常样本的误检，如何降低异常样本的漏检是更为重要的问题. 因此模型4增加了Larea来对背景重构区域进行额外约束，使得漏检率再度下降6.37个百分点，但同时误检率上升11.33个百分点，这说明背景建模的额外约束提升了模型对异常物体检测的性能，但降低了模型的泛化性能，导致误检率上升. 最终模型5在模型4的基础上增加Llocal，进一步强化模型对于异常物体表示的学习，让模型的漏检率下降8.64个百分点，同时漏检率达到0%，让最终模型能够在较低误检的前提下，检测出全部异常物体.
表 9 消融实验Table 9. Ablation ExperimentAD-BFCM模型 阶段建模 干净背景 Larea Llocal 漏检率/% 误检率/% 模型1 – – – – 21.54 35.62 模型2 + – – – 17.83 23.24 模型3 + + – – 9.09 2.17 模型4 + + + – 2.72 13.50 模型5 + + + + 0 4.86 注：“+”代表使用；“−”代表不使用. 本节的实验结果表明，AD-BFCM中的各个模块对模型都有正面的性能提升. 其中分阶段场景建模和图像-背景对的引入让模型能够重构真实场景图片. Llocal和Larea能够帮助模型更好地学习异常物体的表示，让模型获得更好的异常检测效果.
4.5.4 超参数实验
本节实验对背景建模阶段中Larea和前景建模阶段中Llocal的权重设置不同取值并进行实验以验证参数对模型的影响，如表10和表11所示. 经过测试后可以发现，Larea和Llocal参数的比值为5∶1时，模型效果达到最好，这说明模型Llocal参数更加敏感. 在Llocal参数取值较小时，模型误检率会上升；在Larea参数取值较小时，模型漏检率会上升. 由此可以看出，Larea对漏检率有较大影响，而Llocal对误检率有较大影响，这说明背景重构性能对漏检率有较大影响，而前景重构性能对误检率有较大影响.
表 10 背景建模阶段的超参数实验结果Table 10. Hyperparameter Experiment Results in Background Modeling Stage模型 Larea 权重 Llocal 权重 漏检率/% 误检率/% AD-BFCM 0.2 1 5.83 6.47 AD-BFCM 1.0 1 2.72 5.63 AD-BFCM 5.0 1 0 4.86 表 11 前景建模阶段的超参数实验结果Table 11. Hyperparameter Experiment Results in Foreground Modeling Stage模型 Larea 权重 Llocal 权重 漏检率/% 误检率/% AD-BFCM 5 5.0 1.81 5.09 AD-BFCM 5 0.2 0 7.28 AD-BFCM 5 1 0 4.86 4.5.5 数据扩充对实验效果的影响
本节对合成规则进行实验以验证不同规则对模型性能的影响. 值得注意的是，合成规则中的前景比例和前景缩放是基于数据集驱动的，故而本节仅探讨存在异常比例、前景旋转和背景旋转对模型性能的影响.
表12展示了数据集规则中前景旋转和背景旋转对于模型性能的影响. 实验结果表明，当添加前景旋转后，模型漏检率和误检率均出现0.9个百分点以上的下降，说明前景旋转让模型更好地学习到了异常物体的表示，同时增强了泛化性能. 而当添加背景旋转后，模型漏检率和误检率出现大幅上升，这说模型难以学习到剧烈变化下背景的表示.
表 12 基于旋转规则的数据扩充对模型的影响Table 12. Impact of Data Augmentation on Model Based on Rotation Rules前景旋转 背景旋转 漏检率/% 漏检率/% – – 0.90 6.80 + – 0 4.86 + + 4.54 8.79 注：“+”表示使用该项数据扩充，“-”表示不使用该项数据扩充. 表13展示了数据集规则中存在异常比例对于模型性能的影响. 通过实验可以看出，当存在异常比例较高时，模型的误检率相对较高，而漏检率却会下降. 这说明更多的异常前景会让模型学到更好的表示，但同时也会增加模型的误检. 故在真实场景中应用合成数据集时，需对存在异常比例进行额外调整.
表 13 基于存在异常比例规则的数据扩充对模型的影响Table 13. Impact of Data Augmentation on Model Based on Abnormal Proportion Rules存在异常比例 漏检率/% 误检率/% 0.1 0.9 4.53 0.2 0 4.86 0.3 0 5.03 0.4 0 5.53 0.5 0 6.13 综合上述，AD-BFCM在真实场景中有着良好的性能表现：异常检测实验体现了模型的有效性；消融实验表明模型的各个模块对于模型性能有正向提升；参数敏感实验表明适合的超参数能辅助模型更好地进行异常检测；对数据扩充的实验表明模型在面对不同场景时，通过分析真实数据修改合成规则参数可以辅助模型更好地区分异常样本和正常样本的表征.
5. 结 论
基于深度学习的异常检测是当前工业界着重关注的应用研究之一. 工业生产环境中的异常检测问题，往往存在数据标注少、场景多样等问题. 然而，当前的诸多研究很少有涉及数据标注、多场景迁移等问题的讨论，使得检测效果在实际应用场景下往往表现不尽如人意. 基于此，本文提出了基于背景-前景组成式建模的异常检测模型，重点研究多种电路板装配场景中的异常检测问题. 本文将电路板场景的背景和前景分别进行建模：首先采用类似U-net结构的编解码器，配合约束局部区域面积的损失函数完成对背景的建模；然后采用基于生成的组成式建模方法，配合局部前景的重构损失函数，通过多次迭代完成对前景的建模；最后模型通过前景建模过程中的存在表示来完成异常检测.
同时，本文模拟工业生产环境中标注数量少、标注不及时的情况，借助现实装配环境构建了一个包含9个场景的电路板数据集，并提出一种仅需少量标注的数据合成方法. 本文模型在合成数据集上进行训练，并在电路板数据集上进行测试，实验结果表明本文方法能够检测出电路板数据集中的异常物体，具备在工业生产中应用的可行性. 今后，本文将增加更多不同的应用场景，如缺陷检测场景、安全监控场景等，将背景和前景异常物体进一步解耦，构建一个能够动态适应各种复杂应用场景的异常物体检测方法.
作者贡献声明：傅冰飞提出了算法思路、完成主体实验并撰写论文；陈同林负责修改论文；许枫负责提供数据集；朱麟、李斌和薛向阳提出指导意见并参与修改论文.
-
![]()
图 1 无向图上反馈集和子集反馈集问题的归约关系
Figure 1. Reductions among feedback set and subset feedback set problems in undirected graphs
![]()
图 2 有向图上反馈集与子集反馈集问题的归约关系
Figure 2. Reductions among feedback set and subset feedback set problems in directed graphs
![]()
图 3 节点多路割到R-DSFVS的多项式时间归约示意图
Figure 3. Illustrations of the polynomial-time reduction from node multiway cut to R-DSFVS
表 1 反馈集问题类别
Table 1 Variants of Feedback Set Problems
图类型 反馈集 问题简称 无向图 点集 FVS 无向图 边集 FES 有向图 点集 DFVS 有向图 边集 DFAS 
下载: 导出CSV
表 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
表 3 子集反馈集问题在 \mathit{l} 为常数时的计算复杂性
Table 3 Complexity of Subset Feedback Set Problem When \mathit{l} is a Constant
下载: 导出CSV
表 4 度有界的图上的反馈集问题的计算复杂性
Table 4 Complexity of Feedback Set Problems in Degree Bounded Graphs
下载: 导出CSV
表 5 平面图上的反馈集和子集反馈集问题的计算复杂性
Table 5 Complexity of Feedback Set and Subset Feedback Set Problems in Planar Graphs
下载: 导出CSV
表 6 竞赛图和二部竞赛图上的反馈集和子集反馈集问题的计算复杂性
Table 6 Complexity of Feedback Set and Subset Feedback Set Problems in Tournaments and Bipartite Tournaments
下载: 导出CSV
表 7 相交图上的反馈集和子集反馈集问题的计算复杂性
Table 7 Complexity of Feedback Set and Subset Feedback Set Problems in Intersection Graphs
下载: 导出CSV
表 8 禁止图图类上反馈集和子集反馈集问题的计算复杂性
Table 8 Complexity of Feedback Set and Subset Feedback Set Problems in Forbidden Graphs
下载: 导出CSV
表 9 二部图图类上反馈集和子集反馈集问题的计算复杂性
Table 9 Complexity of Feedback Set and Subset Feedback Set Problems in Bipartite Graph Classes
下载: 导出CSV
-
[1] 王建新,江国红,李文军,等. 反馈集问题的研究进展[J]. 计算机科学,2011,38(1):40−47 doi: 10.3969/j.issn.1002-137X.2011.01.008 Wang Jianxin, Jiang Guohong, Ling Wenjun, et al. Algorithms for feedback set problems: A survey[J]. Computer Science, 2011, 38(1): 40−47 (in Chinese) doi: 10.3969/j.issn.1002-137X.2011.01.008
[2] Stephen H U. A study of asynchronous logical feedback networks, technical reports vol. 320[R]. Cambridge, MA: Massachusetts Institute of Technology, Research Laboratory of Electronics, 1957
[3] Zhao Qiulan. Ranking tournaments with no errors[D]. Hong Kong: University of Hong Kong, 2017
[4] Ailon N, Charikar M, Newman A. Aggregating inconsistent information: Ranking and clustering[J]. Journal of the ACM, 2008, 55(5): 1−27
[5] Kunzmann A, Wunderlich H J. An analytical approach to the partial scan problem[J]. Journal of Electronic Testing, 1990, 1(2): 163−174 doi: 10.1007/BF00137392
[6] Kim J L, Peled U N, Perepelitsa I, et al. Explicit construction of families of LDPC codes with no 4-cycles[J]. IEEE Transactions on Information Theory, 2004, 50(10): 2378−2388 doi: 10.1109/TIT.2004.834760
[7] Park H, Hong S, No J S, et al. Design of multiple-edge protographs for QC LDPC codes avoiding short inevitable cycles[J]. IEEE Transactions on Information Theory, 2013, 59(7): 4598−4614 doi: 10.1109/TIT.2013.2250574
[8] Minoura T. Deadlock avoidance revisited[J]. Journal of the ACM, 1982, 29(4): 1023−1048 doi: 10.1145/322344.322351
[9] 曹玖新,高庆清,夏蓉清,等. 社交网络信息传播预测与特定信息抑制[J]. 计算机研究与发展,2021,58(7):1490−1503 doi: 10.7544/issn1000-1239.2021.20200809 Cao Jiuxin, Gao Qingqing, Xia Rongqing, et al. Information propagation prediction and specific information suppression in social networks[J]. Journal of Computer Research and Development, 2021, 58(7): 1490−1503 (in Chinese) doi: 10.7544/issn1000-1239.2021.20200809
[10] 朱军,胡文波. 贝叶斯机器学习前沿进展综述[J]. 计算机研究与发展,2015,52(1):16−26 doi: 10.7544/issn1000-1239.2015.20140107 Zhu Jun, Hu Wenbo. Recent advances in Bayesian machine learning[J]. Journal of Computer Research and Development, 2015, 52(1): 16−26 (in Chinese) doi: 10.7544/issn1000-1239.2015.20140107
[11] 崔焕庆,吴哲辉. 并行程序Petri网模型的结构性质[J]. 计算机研究与发展,2007,44(12):2130−2135 doi: 10.1360/crad20071220 Cui Huanqing, Wu Zhehui. Structural properties of parallel program's Petri net model[J]. Journal of Computer Research and Development, 2007, 44(12): 2130−2135 (in Chinese) doi: 10.1360/crad20071220
[12] Kemeny J G. Mathematics without numbers[J]. Daedalus, 1959, 88(4): 577−591
[13] Dechter R. Enhancement schemes for constraint processing: Back-jumping, learning, and cutset decomposition[J]. Artificial Intelligence, 1990, 41(3): 273−312 doi: 10.1016/0004-3702(90)90046-3
[14] Bar-Yehuda R, Geiger D, Naor J, et al. Approximation algorithms for the feedback vertex set problem with applications to constraint satisfaction and Bayesian inference[J]. SIAM Journal on Computing, 1998, 27(4): 942−959 doi: 10.1137/S0097539796305109
[15] Kratsch S, Schweitzer P. Isomorphism for graphs of bounded feedback vertex set number[G]//LNCS 6139: Proc of the 12th Scandinavian Symp and Workshops on Algorithm Theory (SWAT). Berlin: Springer, 1995: 81−92
[16] Karp R. Reducibility among combinatorial problem[C]//Proc of a Symp on the Complexity of Computer Computations. Berlin: Springer, 1972: 85–103
[17] Even G, Naor J, Schieber B, et al. Approximating minimum feedback sets and multicuts in directed graphs[J]. Algorithmica, 1998, 20(2): 151−174 doi: 10.1007/PL00009191
[18] Even G, Naor J, Zosin L. An 8-approximation algorithm for the subset feedback vertex set problem[J]. SIAM Journal on Computing, 2000, 30(4): 1231−1252 doi: 10.1137/S0097539798340047
[19] Xiao Mingyu, Nagamochi H. An FPT algorithm for edge subset feedback edge set[J]. Information Processing Letters, 2012, 112(1/2): 5−9
[20] Chitnis R, Cygan M, Hajiaghayi M, et al. Directed subset feedback vertex set is fixed-parameter tractable[J]. ACM Transactions on Algorithms, 2015, 11(4): 1−28
[21] Iwata Y, Kobayashi Y. Improved analysis of highest-degree branching for feedback vertex set[J]. Algorithmica, 2021, 83(8): 2503−2520 doi: 10.1007/s00453-021-00815-w
[22] Fomin F V, Gaspers S, Lokshtanov D, et al. Exact algorithms via monotone local search[J]. Journal of the ACM, 2019, 66(2): 1−23
[23] Li J, Nederlof J. Detecting feedback vertex sets of size k in O*(2.7 k) time[J]. ACM Transactions on Algorithms, 2022, 18(4): 1−26
[24] Bafna V, Berman P, Fujito T. A 2-approximation algorithm for the undirected feedback vertex set problem[J]. SIAM Journal on Discrete Mathematics, 1999, 12(3): 289−297 doi: 10.1137/S0895480196305124
[25] Chen Jianer, Liu Yang, Lu Songjian, et al. A fixed-parameter algorithm for the directed feedback vertex set problem[J]. Journal of the ACM, 2008, 55(5): 177−186
[26] Razgon I. Computing minimum directed feedback vertex set in O*(1.9977n)[C]//Proc of the 10th Italian Conf on Theoretical Computer Science. Singapore: World Scientific, 2007: 70−81
[27] Seymour P D. Packing directed circuits fractionally[J]. Combinatorica, 1995, 15(2): 281−288 doi: 10.1007/BF01200760
[28] Even G, Naor J, Schieber B, et al. Approximating minimum feedback sets and multi-cuts in directed graphs: Extended summary[G]//LNCS 920: Proc of the 4th Int Conf on Integer Programming and Combinatorial Optimization (IPCO). Berlin: Springer, 1995: 14−28
[29] Lawler E. A comment on minimum feedback arc sets[J]. IEEE Transactions on Circuit Theory, 1964, 11(2): 296−297 doi: 10.1109/TCT.1964.1082291
[30] Bodlaender H L, Fomin F V, Koster A M C A, et al. A note on exact algorithms for vertex ordering problems on graphs[J]. Theory of Computing Systems, 2012, 50(3): 420−432 doi: 10.1007/s00224-011-9312-0
[31] Cygan M, Pilipczuk M, Pilipczuk M, et al. On multiway cut parameterized above lower bounds[J]. ACM Transactions on Computation Theory, 2013, 5(1): 1−11
[32] Karger D R, Klein P, Stein C, et al. Rounding algorithms for a geometric embedding of minimum multiway cut[J]. Mathematics of Operations Research, 2004, 29(3): 436−461. doi: 10.1287/moor.1030.0086
[33] Chen Li, Kyng R, Liu Y P, et al. Maximum flow and minimum-cost flow in almost-linear time[C]//Proc of the 63rd Annual Symp on Foundations of Computer Science (FOCS). Los Alamitos, CA: IEEE Computer Society, 2022: 612−623
[34] Iwata Y, Yamaguchi Y, Yoshida Y. 0/1/all CSPs, half-integral A-path packing, and linear-time FPT algorithms[C]// Proc of the 59th IEEE Annual Symp on Foundations of Computer Science (FOCS). Los Alamitos, CA: IEEE Computer Society, 2018: 462−473
[35] Even G, Naor J, Schieber B, et al. Approximating minimum subset feedback sets in undirected graphs with applications[J]. SIAM Journal on Discrete Mathematics, 2000, 13(2): 255−267 doi: 10.1137/S0895480195291874
[36] Garg N, Vazirani V V, Yannakakis M. Multiway cuts in node weighted graphs[J]. Journal of Algorithms, 2004, 50(1): 49−61 doi: 10.1016/S0196-6774(03)00111-1
[37] Chitnis R, Fomin F V, Lokshtanov D, et al. Faster exact algorithms for some terminal set problems[J]. Journal of Computer and System Sciences, 2017, 88(3): 195−207
[38] Garey M R, Johnson D S. Computers and Intractability: A Guide to the Theory of NP-Completeness[M]. San Francisco, CA: W. H. Freeman, 1979: 191−192
[39] Speckenmeyer E. Untersuchungen zum feedback vertex set problem in ungerichteten graphen[D]. Paderborn: Universität Paderborn, 1983
[40] Ueno S, Kajitani Y, Gotoh S. On the nonseparating independent set problem and feedback set problem for graphs with no vertex degree exceeding three[J]. Discrete Mathematics, 1988, 72(1/2/3): 355−360
[41] Gabow H N, Stallmann M. Efficient algorithms for graphic matroid intersection and parity (extended abstract)[G]∥LNCS 194: Proc of the 12th Int Colloquium on Automata, Languages, and Programming (ICALP). Berlin: Springer, 1985: 210−220
[42] Yannakais M. Node-and edge-deletion NP-complete problems[C]//Proc of the 10th Annual ACM Symp on Theory of Computing (STOC). New York: ACM, 1978: 253−264
[43] Lucchesi C L, Younger D H. A minimax theorem for directed graphs[J]. Journal of the London Mathematical Society, 1978, 2(3): 369−374
[44] Gabow H N. A framework for cost-scaling algorithms for submodular flow problems[C]//Proc of the 34th Annual Symp on Foundations of Computer Science (FOCS). Los Alamitos, CA: IEEE Computer Society, 1993: 449−458
[45] Cavallaro von D. Hamiltonicity and the computational complexity of graph problems[D]. Berlin: Technische Universität Berlin, 2019
[46] Appel K, Haken W. Every planar map is four colorable. Part I: Discharging[J]. Illinois Journal of Mathematics, 1977, 21(3): 429−490
[47] Appel K, Haken W, Koch J. Every planar map is four colorable. Part II: Reducibility[J]. Illinois Journal of Mathematics, 1977, 21(3): 491−567
[48] Robertson N, Sanders D P, Seymour P, et al. Efficiently four-coloring planar graphs[C]//Proc of the 28th Annual ACM Symp on Theory of Computing (STOC). New York: ACM, 1996: 571−575
[49] Speckenmeyer E. On feedback problems in digraphs[G]//LNCS 484: Proc of the 15th Int Workshop of Graph-Theoretic Concepts in Computer Science (WG). Berlin: Springer. 1989: 218−231
[50] Cai Maocheng, Deng Xiaotie, Zang Wenan. A min-max theorem on feedback vertex sets[J]. Mathematics of Operations Research, 2002, 27(2): 361−371 doi: 10.1287/moor.27.2.361.328
[51] Alon N. Ranking tournaments[J]. SIAM Journal on Discrete Mathematics, 2006, 20(1): 137−142 doi: 10.1137/050623905
[52] Charbit P, Thomasse S, Yeo A. The minimum feedback arc set problem is NP-hard for tournaments[J]. Combinatorics, Probability and Computing, 2007, 16(1): 1−4 doi: 10.1017/S0963548306007887
[53] Conitzer V. Computing Slater rankings using similarities among candidates[C]//Proc of the 21st National Conf on Artificial Intelligence (AAAI). Palo Alto, CA: AAAI, 2006: 613−619
[54] Guo Jong, Huffner F, Moser H. Feedback arc set in bipartite tournaments is NP-complete[J]. Information Processing Letters, 2007, 102(2/3): 62−65
[55] Brandstädt A, Kratsch D. On the restriction of some NP-complete graph problems to permutation graphs[G]//LNCS 199: Proc of the Int Conf on Fundamentals of Computation Theory (FCT). Berlin: Springer, 1985: 53−62
[56] Brandstädt A, Kratsch D. On domination problems for permutation and other graphs[J]. Theoretical Computer Science, 1987, 54(2/3): 181−198
[57] Brandstädt A. On improved time bounds for permutation graph problems[G]//LNCS 657: Proc of the 18th Int Workshop Graph-Theoretic Concepts in Computer Science (WG). Berlin: Springer, 1992: 1−10
[58] Liang Y D. On the feedback vertex set problem in permutation graphs[J]. Information Processing Letters, 1994, 52(3): 123−129 doi: 10.1016/0020-0190(94)00133-2
[59] Honma H, Kitamura Y, Masuyama S. An algorithm for minimum feedback vertex set problem on a trapezoid graph[J]. IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences, 2011, 94(6): 1381−1385
[60] Takaoka A, Yayu S, Ueno S. On minimum feedback vertex sets in bipartite graphs and degree-constraint graphs[J]. IEICE Transactions on Information and Systems, 2013, 96(11): 2327−2332
[61] Coorg S R, Rangan C P. Feedback vertex set on cocomparability graphs[J]. Networks, 1995, 26(2): 101−111 doi: 10.1002/net.3230260205
[62] Liang Y D, Chang Mawshang. Minimum feedback vertex sets in cocomparability graphs and convex bipartite graphs[J]. Acta Informatica, 1997, 34(5): 337−346 doi: 10.1007/s002360050088
[63] Gavril F. Minimum weight feedback vertex sets in circle n-gon graphs and circle trapezoid graphs[J]. Discrete Mathematics, Algorithms and Applications, 2011, 3(3): 323−336 doi: 10.1142/S1793830911001243
[64] Papadopoulos C, Tzimas S. Polynomial-time algorithms for the subset feedback vertex set problem on interval graphs and permutation graphs[J]. Discrete Applied Mathematics, 2019, 258(4): 204−221
[65] Yannakakis M, Gavril F. The maximum k-colorable subgraph problem for chordal graphs[J]. Information Processing Letters, 1987, 24(2): 133−137 doi: 10.1016/0020-0190(87)90107-4
[66] Lu Chinlung, Tang Chuanyi. A linear-time algorithm for the weighted feedback vertex problem on interval graphs[J]. Information Processing Letters, 1997, 61(2): 107−111 doi: 10.1016/S0020-0190(96)00193-7
[67] Fomin F V, Heggernes P, Kratsch D, et al. Enumerating minimal subset feedback vertex sets[J]. Algorithmica, 2014, 69(1): 216−231 doi: 10.1007/s00453-012-9731-6
[68] Bai Tian, Xiao Mingyu. Exact and parameterized algorithms for restricted subset feedback vertex set in chordal graphs[G]//LNCS 13571: Proc of the 17th Annual Conf on Theory and Applications of Models of Computation (TAMC). Berlin: Springer, 2023: 249−261
[69] Marathe M V, Ravi R, Rangan C P. Generalized vertex covering in interval graphs[J]. Discrete Applied Mathematics, 1992, 39(1): 87−93 doi: 10.1016/0166-218X(92)90116-R
[70] Kratsch D, Muller H, Todinca I. Feedback vertex set on AT-free graphs[J]. Discrete Applied Mathematics, 2008, 156(10): 1936−1947 doi: 10.1016/j.dam.2007.10.006
[71] Poljak S. A note on stable sets and colorings of graphs[J]. Commentationes Mathematicae Niversitatis Carolinae, 1974, 15(2): 307−309
[72] Munaro A. On line graphs of subcubic triangle-free graphs[J]. Discrete Mathematics, 2017, 340(6): 1210−1226 doi: 10.1016/j.disc.2017.01.006
[73] Chiarelli N, Hartinger T R, Johnson M, et al. Minimum connected transversals in graphs: New hardness results and tractable cases using the price of connectivity[J]. Theoretical Computer Science, 2018, 705: 75−83 doi: 10.1016/j.tcs.2017.09.033
[74] Dabrowski K K, Fehali C, Johnson M, et al. On cycle transversals and their connected variants in the absence of a small linear forest[J]. Algorithmica, 2020, 82(10): 2841−2866 doi: 10.1007/s00453-020-00706-6
[75] Abrishami T, Chudnovsky M, Pilipczuk M, et al. Induced subgraphs of bounded treewidth and the container method[C]//Proc of the 2021 ACM-SIAM Symp on Discrete Algorithms (SODA). Philadelphia, PA: SIAM, 2021: 1948−1964
[76] Paesani G, Paulusma D, Rzazwski P. Feedback vertex set and even cycle transversal for H-free graphs: Finding large block graphs[J]. SIAM Journal on Discrete Mathematics, 2022, 36(4): 2453−2472 doi: 10.1137/22M1468864
[77] Paesani G, Paulusma D, Rzazwski P. Classifying subset feedback vertex set for H-free graphs[G]//LNCS 13453: Proc of the 48th Int Workshop Graph-Theoretic Concepts in Computer Science (WG). Berlin: Springer, 2022: 412−424
[78] Jiang Wei, Liu Tian, Xu Ke. Tractable feedback vertex sets in restricted bipartite graphs[G]//LNCS 6831: Proc of the 5th Int Conf Combinatorial Optimization and Applications (COCOA). Berlin: Springer, 2011: 424−434
[79] Jiang Wei, Liu Tian, Ren Tienan, et al. Two hardness results on feedback vertex sets[G]//LNCS 6681: Proc of Joint Int Conf on Frontiers in Algorithmics and Algorithmic Aspects in Information and Management (FAW-AAIM). Berlin: Springer, 2011: 233−243
[80] Kloks T, Liu Chinghao, Poon Sheunghung. Feedback vertex set on chordal bipartite graphs[J]. arXiv preprint, arXiv: 1104.3915, 2011
[81] Jiang Wei, Liu Tian, Wang Chaoyi, et al. Feedback vertex sets on restricted bipartite graphs[J]. Theoretical Computer Science, 2013, 507: 41−51 doi: 10.1016/j.tcs.2012.12.021
[82] Liu Tian, Lu Min, Lu Zhao, et al. Circular convex bipartite graphs: Feedback vertex sets[J]. Theoretical Computer Science, 2014, 556: 55−62 doi: 10.1016/j.tcs.2014.05.001
计量
- 文章访问数: 138
- HTML全文浏览量: 21
- PDF下载量: 36
