反馈集问题的研究进展  

Algorithms for Feedback Set Problems:A Survey

作　　者：王建新[1] 江国红[1] 李文军[1] 陈建二[1] 

机构地区：[1]中南大学信息科学与工程学院,长沙410083

出　　处：《计算机科学》2011年第1期40-47,共8页Computer Science

基　　金：国家自然科学基金(60773111);国家教育部创新团队资助计划(IRT0661)资助

摘　　要：反馈集问题是经典的NP难问题,在电路测试、操作系统解死锁、分析工艺流程、生物计算等领域都有重要应用,按照反馈集中元素类型可分为反馈顶点集(FVS)问题和反馈边集(FAS)问题。人们利用线性规划和局部搜索等技术设计了一系列关于FVS和FAS问题的近似算法,并基于分枝-剪枝策略和加权分治技术提出了FVS问题的精确算法。随着参数计算理论的发展,近年来参数化反馈集问题引起了人们的重视,并取得了很大突破。目前已经证明了无向图和有向图中FVS问题和FAS问题都是固定参数可解的(FPT)。利用树分解、分支搜索、迭代压缩等技术,对无向图FVS问题提出了一系列FPT算法。针对某些特殊的应用,人们开展了对具有特殊性质的图上FVS问题的研究,提出了一些多项式时间可解的精确算法。现首先介绍了在无向图中关于FVS问题的近似算法与精确算法,然后具体分析了FVS问题的参数化算法。进一步阐述了关于有向图和特殊图上FVS问题的研究现状,介绍了FAS问题的研究成果。基于对反馈集问题研究现状的分析,提出了今后FVS问题研究中值得关注的几个方面。Feedback Set problems are classical NP problems,which include Feedback Vertex Set（FVS） and Feedback Arc Set（FAS） problems.There are important applications of these problems in many fields,such as circuit testing,deadlock resolution,analyzing manufacturing processes and computational biology.People have designed many different approximate algorithms based on linear programming and local search approaches,and have found exact solutions by Branch-Prune and Measure-and-Conquer techniques.Recently,Parameterized Feedback Set problems have received considerable attention.The development of parameterized complexity motivates the studies on parameterized Feedback Set problems,especially on parameterized FVS problem.A chain of dramatic improvements on FVS problem in undirected graphs were obtained using different methods,such as tree decomposition,branch-and-search,iterative compression.In this paper,the approximation algorithms and parameter algorithms about FVS problem in general undirected graphs were introduced firstly.Then the research on the FVS problem in directed graphs and special graphs were presented.Moreover,the FAS problems were also discussed.Finally,some future researches with considerable attention on FVS problems were proposed by analyzing the researches on feedback set problems.

关 键 词：反馈顶点集 反馈边集 近似算法 精确算法 参数算法 

分 类 号：TP301.6[自动化与计算机技术—计算机系统结构]