Approximating Minimum Subset Feedback Sets in Undirected Graphs with Applications

DOI10.1137/S0895480195291874zbMath0941.68057MaRDI QIDQ4490783

Baruch Schieber, Joseph (Seffi) Naor, Guy Even, Leonid Zosin

Publication date: 20 July 2000

Published in: SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/s0895480195291874

zbMATH Keywords

combinatorial optimization; approximation algorithms; feedback vertex set; multicut; feedback edge set; subset feedback set

Mathematics Subject Classification ID

68Q25: Analysis of algorithms and problem complexity

68R10: Graph theory (including graph drawing) in computer science

05C85: Graph algorithms (graph-theoretic aspects)

68W25: Approximation algorithms

Related Items

Primal-dual approximation algorithms for feedback problems in planar graphs, A primal-dual approximation algorithm for the vertex cover \(P^3\) problem, Partitioning series-parallel multigraphs into \(v^*\)-excluding edge covers, On the minimum feedback vertex set problem: Exact and enumeration algorithms, A primal-dual interpretation of two 2-approximation algorithms for the feedback vertex set problem in undirected graphs, A randomized polynomial kernel for subset feedback vertex set, A factor \(2\) approximation algorithm for the vertex cover \(P_3\) problem, Local search is a PTAS for feedback vertex set in minor-free graphs, Control of Boolean networks: hardness results and algorithms for tree structured networks, Clustering with qualitative information, Subset Feedback Vertex Set Is Fixed-Parameter Tractable