×

zbMATH — the first resource for mathematics

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.

MSC:
90C35 Programming involving graphs or networks
PDF BibTeX Cite
Full Text: DOI
References:
[1] V. Bafna, P. Berman, 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, number 1004 in Lecture Notes in Computer Science, Springer, Berlin, 1995, pp. 142-151.
[2] R. Bar-Yehuda, D. Geiger, J. Naor, R.M. Roth, Approximation algorithms for the vertex feedback set problem with applications to constraint satisfaction and Bayesian inference, in: Proc. 5th Ann. ACM-SIAM Symp. on Discrete Algorithms, 1994, pp. 344-354. · Zbl 0867.05073
[3] A. Becker, D. Geiger, Approximation algorithms for the loop cutset problem, in: Proc. 10th Conf. on Uncertainty in Artificial Intelligence, 1994, pp. 60-68. Update: A. Becker, D. Geiger: Optimization of Pearl’s method of conditioning and greedy-like approximation algorithms for the vertex feedback set problem, Artificial Intelligence 83 (1996), 167-188.
[4] G. Even, J. Naor, B. Schieber, L. Zosin, Approximating minimum subset feedback sets in undirected graphs with applications, in: Proc. 4th Israel Symp. on Theory of Computing and Systems, 1996, pp. 78-88. · Zbl 0941.68057
[5] M.R. Garey, D.S. Johnson, Computers and Intractability, W.H. Freeman and Company, New York, 1979.
[6] M.X. Goemans, D.P. Williamson, Primal – dual approximation algorithms for feedback problems in planar graphs, in: W.H. Cunningham, S.T. McCormick, M. Queyranne (Eds.), Integer Programming and Combinatorial Optimization, number 1084, in Lecture Notes in Computer Science, Springer, Berlin, 1996, pp. 147-161, to appear in Combinatorica. · Zbl 1415.90101
[7] M.X. Goemans, D.P. Williamson, The primal – dual method for approximation algorithms and its application to network design problems, in: D.S. Hochbaum (Ed.), Approximation Algorithms for NP-hard Problems, Ch. 4, PWS, Boston, 1996.
[8] D.S. Hochbaum, Approximating covering and packing problems: Set cover, vertex cover, independent set, and related problems, in: D.S. Hochbaum (Ed.), Approximation Algorithms for NP-hard Problems, Ch. 3, PWS, Boston, 1996.
[9] P. Klein, R. Ravi, When cycles collapse: a general approximation technique for constrained two-connectivity problems, in: Proc. 3rd MPS Conf. on Integer Programming and Combinatorial Optimization, 1993, pp. 39-55, also appears as Brown University Technical Report CS-92-30, to appear in Algorithmica. · Zbl 0942.68651
[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.