Feedback set problems

In recent years feedback set problems have been the subject of growing interest. They have found applications in many fields, including deadlock prevention, program verification, and Bayesian inference. Therefore, it is natural that in the past few years there have been intensive efforts on exact and approximation algorithms for these kinds of problems. It generalizes a number of problems, including the minimum feedback vertex (arc) set problem in both directed and undirected graphs, the subset minimum feedback vertex (arc) set problem and the graph bipartization problem, in which one must remove a minimum-weight set of vertices so that the remaining graph is bipartite. The scope of this article is to give a complete state-of-art survey of exact and approximation algorithms and to analyze a new practical heuristic method called GRASP for solving both feedback vertex and feedback arc set problems.