An 8-Approximation Algorithm for the Subset Feedback Vertex Set Problem

DOI10.1137/S0097539798340047zbMath0973.05073OpenAlexW2171796957MaRDI 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

zbMATH Keywords

combinatorial optimizationapproximation algorithmsmulticommodity flowfeedback vertex setmulticut

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Linear programming (90C05) Graph theory (including graph drawing) in computer science (68R10) Graph algorithms (graph-theoretic aspects) (05C85) Applications of graph theory to circuits and networks (94C15) Approximation algorithms (68W25)

Related Items (24)

Parameterized Vertex Deletion Problems for Hereditary Graph Classes with a Block Property ⋮ Designing FPT Algorithms for Cut Problems Using Randomized Contractions ⋮ A parameterized algorithm for subset feedback vertex set in tournaments ⋮ Exact and parameterized algorithms for restricted subset feedback vertex set in chordal graphs ⋮ Exact algorithms for restricted subset feedback vertex set in chordal and split graphs ⋮ A randomized polynomial kernel for subset feedback vertex set ⋮ Unnamed Item ⋮ Fixed-parameter tractability for the subset feedback set problem and the \(S\)-cycle packing problem ⋮ Packing cycles through prescribed vertices under modularity constraints ⋮ Subset feedback vertex sets in chordal graphs ⋮ Enumerating minimal subset feedback vertex sets ⋮ Finding temporal paths under waiting time constraints ⋮ Subset Feedback Vertex Set Is Fixed-Parameter Tractable ⋮ Half-integral packing of odd cycles through prescribed vertices ⋮ Disjoint cycles intersecting a set of vertices ⋮ Polynomial-time algorithms for the subset feedback vertex set problem on interval graphs and permutation graphs ⋮ Mim-width. II. The feedback vertex set problem ⋮ The k-Observer Problem on d-regular Graphs ⋮ Subset feedback vertex set in chordal and split graphs ⋮ Subset feedback vertex set on graphs of bounded independent set size ⋮ An FPT algorithm for edge subset feedback edge set ⋮ Graphs without two vertex-disjoint \(S\)-cycles ⋮ Node multiway cut and subset feedback vertex set on graphs of bounded mim-width ⋮ Fixed-parameter tractability for subset feedback set problems with parity constraints

This page was built for publication: An 8-Approximation Algorithm for the Subset Feedback Vertex Set Problem