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

Abstract: 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.

Key words: Feedback vertex set, Feedback are set, Approximation algorithm, Exact algorithm, Parameterized algorithm