TY - JOUR

T1 - A 2-Approximation algorithm for the undirected feedback vertex set problem

AU - Bafna, Vineet

AU - Berman, Piotr

AU - Fujito, Toshihiro

PY - 1999/9

Y1 - 1999/9

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=0000113012&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=0000113012&partnerID=8YFLogxK

U2 - 10.1137/S0895480196305124

DO - 10.1137/S0895480196305124

M3 - Article

AN - SCOPUS:0000113012

SN - 0895-4801

VL - 12

SP - 289

EP - 297

JO - SIAM Journal on Discrete Mathematics

JF - SIAM Journal on Discrete Mathematics

IS - 3

ER -