An 8-approximation algorithm for the subset feedback vertex set problem

被引:39
作者
Even, G [1 ]
Naor, JS
Zosin, L
机构
[1] Tel Aviv Univ, Dept Elect Engn, IL-69978 Tel Aviv, Israel
[2] Technion Israel Inst Technol, Dept Comp Sci, IL-32000 Haifa, Israel
[3] ITG Inc, Boston, MA 02210 USA
关键词
approximation algorithms; combinatorial optimization; feedback vertex set; multicommodity flow; multicut;
D O I
10.1137/S0097539798340047
中图分类号
TP301 [理论、方法];
学科分类号
081202 ;
摘要
We present an 8-approximation algorithm for the problem of finding a minimum weight subset feedback vertex set ( or SUBSET-FVS, in short). The input in this problem consists of an undirected graph G = (V, E) with vertex weights c(v) and a subset of vertices S called special vertices. A cycle is called interesting if it contains at least one special vertex. A subset of vertices is called a SUBSET-FVS with respect to S if it intersects every interesting cycle. The goal is to nd a minimum weight SUBSET-FVS. The best previous algorithm for the general case provided only a logarithmic approximation factor. The minimum weight SUBSET-FVS problem generalizes two NP-complete problems: the minimum weight feedback vertex set problem in undirected graphs and the minimum weight multiway vertex cut problem. The main tool that we use in our algorithm and its analysis is a new version of multicommodity ow, which we call relaxed multicommodity flow. Relaxed multicommodity ow is a hybrid of multicommodity ow and multiterminal flow.
引用
收藏
页码:1231 / 1252
页数:22
相关论文
共 21 条
[1]  
AHUJA RK, 1993, NETWORK FLOUS
[2]  
[Anonymous], 1979, Computers and Intractablity: A Guide to the Theoryof NP-Completeness
[3]   A 2-approximation algorithm for the undirected feedback vertex set problem [J].
Bafna, V ;
Berman, P ;
Fujito, T .
SIAM JOURNAL ON DISCRETE MATHEMATICS, 1999, 12 (03) :289-297
[4]   Optimization of Pearl's method of conditioning and greedy-like approximation algorithms for the vertex feedback set problem [J].
Becker, A ;
Geiger, D .
ARTIFICIAL INTELLIGENCE, 1996, 83 (01) :167-188
[5]  
Calinescu G., 1998, Proceedings of the Thirtieth Annual ACM Symposium on Theory of Computing, P48, DOI 10.1145/276698.276711
[6]   THE COMPLEXITY OF MULTITERMINAL CUTS [J].
DAHLHAUS, E ;
JOHNSON, DS ;
PAPADIMITRIOOU, CH ;
SEYMOUR, PD ;
YANNAKAKIS, M .
SIAM JOURNAL ON COMPUTING, 1994, 23 (04) :864-894
[7]   Approximating minimum subset feedback sets in undirected graphs with applications [J].
Even, G ;
Naor, JS ;
Schieber, B ;
Zosin, L .
SIAM JOURNAL ON DISCRETE MATHEMATICS, 2000, 13 (02) :255-267
[8]   Approximating minimum feedback sets and multicuts in directed graphs [J].
Even, G ;
Naor, J ;
Schieber, B ;
Sudan, M .
ALGORITHMICA, 1998, 20 (02) :151-174
[9]  
Even G, 1995, AN S FDN CO, P62, DOI 10.1109/SFCS.1995.492463
[10]  
EVEN G, IN PRESS J ACM