A primal–dual interpretation of two 2-approximation algorithms for the feedback vertex set problem in undirected graphs

Recently, Becker and Geiger and Bafna, Berman and Fujito gave 2-approximation algorithms for the feedback vertex set problem in undirected graphs. We show how their algorithms can be explained in terms of the primal–dual method for approximation algorithms, which has been used to derive approximatio...

Full description

Saved in:
Bibliographic Details
Published in:Operations research letters 1998-05, Vol.22 (4), p.111-118
Main Authors: Chudak, Fabián A., Goemans, Michel X., Hochbaum, Dorit S., Williamson, David P.
Format: Article
Language:English
Subjects:
Applied sciences
Approximation algorithms
Combinatorial optimization
Exact sciences and technology
Feedback vertex set
Flows in networks. Combinatorial problems
Operational research and scientific management
Operational research. Management science
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:Recently, Becker and Geiger and Bafna, Berman and Fujito gave 2-approximation algorithms for the feedback vertex set problem in undirected graphs. We show how their algorithms can be explained in terms of the primal–dual method for approximation algorithms, which has been used to derive approximation algorithms for network design problems. In the process, we give a new integer programming formulation for the feedback vertex set problem whose integrality gap is at worst a factor of two; the well-known cycle formulation has an integrality gap of Θ( log n) , as shown by Even, Naor, Schieber and Zosin. We also give a new 2-approximation algorithm for the problem which is a simplification of the Bafna et al. algorithm.
ISSN:0167-6377
1872-7468
DOI:10.1016/S0167-6377(98)00021-2