TY - GEN
T1 - Approximating minimum feedback sets andmulti-cuts in directed graphs
AU - Even, Guy
AU - Naor, Joseph Seffi
AU - Schieber, Baruch
AU - Sudan, Madhu
N1 - Publisher Copyright:
© Springer-Verlag Berlin Heidelberg 1995.
PY - 1995
Y1 - 1995
N2 - This paper deals with approximating feedback sets in directed graphs. We consider two related problems: the weighted feedback vertex set (FVS) problem, and the weighted feedback edge set problem (FBS). In the FVS (resp. FES) problem, one is given a directed graph with weights on the vertices (resp. edges), and is asked to find a subset of vertices (resp. edges) with minimum total weight that intersects every directed cycle in the graph. These problems are among the classical NP-Hard problems and have many applications. We also consider a generalization of these problems: SUBSET-FVS and SUBSBT-FZS, in which the feedback set has to intersect only a subset of the directed cycles in the graph. This subset contains all the cycles that go through a distinguished input subset of vertices and edges. We present approximation algorithms for all four problems that achieve an approximation factor of O(min{log τ loglog τ *,log nloglog n)}, where τ * denotes the value of the optimum fractional solution of the problem at hand. For the SUBSBT-FVS and SUBSET-FBS problems we also give an algorithm that achieves an approximation factor of O(log2 |X|), where X is the subset of distinguished vertices and edges. This algorithm is based on an approximation algorithm for the multi-cut problem in a special type of directed networks. Another contribution of our paper is a combznatomal algorithm that computes a (1 + ε) approximation to the fractional optimal feedback vertex set. Computing the approximate solution is much simpler and more efficient than general linear programming methods. All of our algorithms use this approximate solution.
AB - This paper deals with approximating feedback sets in directed graphs. We consider two related problems: the weighted feedback vertex set (FVS) problem, and the weighted feedback edge set problem (FBS). In the FVS (resp. FES) problem, one is given a directed graph with weights on the vertices (resp. edges), and is asked to find a subset of vertices (resp. edges) with minimum total weight that intersects every directed cycle in the graph. These problems are among the classical NP-Hard problems and have many applications. We also consider a generalization of these problems: SUBSET-FVS and SUBSBT-FZS, in which the feedback set has to intersect only a subset of the directed cycles in the graph. This subset contains all the cycles that go through a distinguished input subset of vertices and edges. We present approximation algorithms for all four problems that achieve an approximation factor of O(min{log τ loglog τ *,log nloglog n)}, where τ * denotes the value of the optimum fractional solution of the problem at hand. For the SUBSBT-FVS and SUBSET-FBS problems we also give an algorithm that achieves an approximation factor of O(log2 |X|), where X is the subset of distinguished vertices and edges. This algorithm is based on an approximation algorithm for the multi-cut problem in a special type of directed networks. Another contribution of our paper is a combznatomal algorithm that computes a (1 + ε) approximation to the fractional optimal feedback vertex set. Computing the approximate solution is much simpler and more efficient than general linear programming methods. All of our algorithms use this approximate solution.
UR - http://www.scopus.com/inward/record.url?scp=84948977289&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=84948977289&partnerID=8YFLogxK
U2 - 10.1007/3-540-59408-6_38
DO - 10.1007/3-540-59408-6_38
M3 - Conference contribution
AN - SCOPUS:84948977289
SN - 9783540594086
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 14
EP - 28
BT - Integer Programming and Combinatorial Optimization - 4th International IPCO Conference, 1995, Proceedings
A2 - Balas, Egon
A2 - Clausen, Jens
PB - Springer Verlag
T2 - 4th International Conference on Integer Programming and Combinatorial Optimization, IPCO 1995
Y2 - 29 May 1995 through 31 May 1995
ER -