SIAM Journal on Discrete Mathematics · 1999 · 349 citations · 8 references
ComputingComputer ScienceMathematicsAlgorithmsCombinatoricsOptimizationApproximation AlgorithmsCombinatorial OptimizationGraph AlgorithmsFeedback Vertex SetVertex Cover Approximation
A feedback vertex set of a graph is a subset of vertices that contains at least one vertex from every cycle in the graph. The problem considered is that of finding a minimum feedback vertex set given a weighted and undirected graph. We present a simple and efficient approximation algorithm with performance ratio of at most 2, improving previous best bounds for either weighted or unweighted cases of the problem. Any further improvement on this bound, matching the best constant factor known for the vertex cover problem, is deemed challenging. The approximation principle, underlying the algorithm, is based on a generalized form of the classical local ratio theorem, originally developed for approximation of the vertex cover problem, and a more flexible style of its application.
8
Proof verification and hardness of approximation problems
Sanjeev Arora, Carsten Lund, R. Motwani et al. · 1992 · 744 citations