Algorithms for Feedback Set Problems:A Survey
反馈集问题的研究进展

Feedback Set problems arc classical NP problems, which include Feedback Vertex Set(FVS) and Feedback Vertex 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 con- siderable 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.