A primal-dual interpretation of two 2-approximation algorithms for the feedback vertex set problem in undirected graphs. (English) Zbl 0920.90137

Summary: Recently, A. Becker and D. Geiger [‘Approximation algorithms for the loop cutset problem’, in: Proc. 10th Conf. on Uncertainty in Artificial Intelligence, 60-68 (1994)] and V. Bafna, P. Berman and T. Fujito [‘Constant ratio approximation of the weighted feedback vertex set problem for undirected graphs’, in: J. Staples, P. Eades, N. Katoh, A. Moffat (eds.), ISAAC ’95, Algorithms and Computation, Lect. Notes Computer Sci. 1004, 142-151 (1995)] 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 \(\Theta(\log n)\), as shown by E. Even, J. Noor, B. Schieber and L. Zosin [‘Approximating minimum subset feedback sets in undirected graphs with applications’, in: Proc. 4th Israel Symp. on Theory of Computing and Systems, 78-88 (1996)]. We also give a new 2-approximation algorithm for the problem which is a simplification of the Bafna et al. algorithm.


90C35 Programming involving graphs or networks
Full Text: DOI


[10] Williamson, D. P.; Goemans, M. X.; Mihail, M.; Vazirani, V. V., A primal-dual approximation algorithm for generalized Steiner network problems, Combinatorica, 15, 435-454 (1995) · Zbl 0838.90133
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.