An 8-Approximation Algorithm for the Subset Feedback Vertex Set Problem
From MaRDI portal
Publication:4507392
DOI10.1137/S0097539798340047zbMath0973.05073MaRDI QIDQ4507392
Joseph (Seffi) Naor, Guy Even, Leonid Zosin
Publication date: 18 October 2000
Published in: SIAM Journal on Computing (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1137/s0097539798340047
combinatorial optimization; approximation algorithms; multicommodity flow; feedback vertex set; multicut
68Q25: Analysis of algorithms and problem complexity
90C05: Linear programming
68R10: Graph theory (including graph drawing) in computer science
05C85: Graph algorithms (graph-theoretic aspects)
94C15: Applications of graph theory to circuits and networks
68W25: Approximation algorithms
Related Items
Unnamed Item, The k-Observer Problem on d-regular Graphs, Polynomial-time algorithms for the subset feedback vertex set problem on interval graphs and permutation graphs, Subset feedback vertex set in chordal and split graphs, Node multiway cut and subset feedback vertex set on graphs of bounded mim-width, A parameterized algorithm for subset feedback vertex set in tournaments, Exact and parameterized algorithms for restricted subset feedback vertex set in chordal graphs, Fixed-parameter tractability for the subset feedback set problem and the \(S\)-cycle packing problem, Packing cycles through prescribed vertices under modularity constraints, Enumerating minimal subset feedback vertex sets, Disjoint cycles intersecting a set of vertices, An FPT algorithm for edge subset feedback edge set, Graphs without two vertex-disjoint \(S\)-cycles, A randomized polynomial kernel for subset feedback vertex set, Finding temporal paths under waiting time constraints, Half-integral packing of odd cycles through prescribed vertices, Mim-width. II. The feedback vertex set problem, Subset feedback vertex set on graphs of bounded independent set size, Fixed-parameter tractability for subset feedback set problems with parity constraints, Subset feedback vertex sets in chordal graphs, Subset Feedback Vertex Set Is Fixed-Parameter Tractable, Parameterized Vertex Deletion Problems for Hereditary Graph Classes with a Block Property, Designing FPT Algorithms for Cut Problems Using Randomized Contractions
