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

DOI10.1137/S0097539798340047MaRDI QIDQ4507392zbMATH OpenOpenAlexFDO

Authors Guy Even, Joseph (Seffi) Naor, 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

approximation algorithmscombinatorial optimizationfeedback vertex setmulticommodity flowmulticut

Mathematics Subject Classification ID

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

Recommendations

• Approximating minimum feedback sets and multi-cuts in directed graphs (extended summary)
• Approximating minimum feedback sets and multicuts in directed graphs
• Approximating Minimum Subset Feedback Sets in Undirected Graphs with Applications
• Constant factor approximation for subset feedback set problems via a new LP relaxation
• Enumerating minimal subset feedback vertex sets

Cited in

(33)

• 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
• Parameterized vertex deletion problems for hereditary graph classes with a block property
• Designing FPT algorithms for cut problems using randomized contractions
• Fixed-parameter tractability for the subset feedback set problem and the \(S\)-cycle packing problem
• Packing cycles through prescribed vertices under modularity constraints
• Approximating Minimum Subset Feedback Sets in Undirected Graphs with Applications
• Constant factor approximation for subset feedback set problems via a new LP relaxation
• Enumerating minimal subset feedback vertex sets
• Subset feedback vertex set on graphs of bounded independent set size
• Approximating minimum feedback sets and multi-cuts in directed graphs (extended summary)
• The \(k\)-observer problem on \(d\)-regular 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
• Exact algorithms for restricted subset feedback vertex set in chordal and split graphs
• Polyhedral aspects of feedback vertex set and pseudoforest deletion set
• Approximate monotone local search for weighted problems
• Combinatorial optimization. Abstracts from the workshop held November 10--15, 2024
• Disjoint cycles intersecting a set of vertices
• Breaking the barrier 2ᵏ for subset feedback vertex set in chordal graphs
• Subset feedback vertex set in tournaments as fast as without the subset
• Solving subset feedback vertex set in chordal graphs faster than 2ᵏ
• Subset feedback vertex set and subset vertex cover on AT-free graphs
• Subset feedback vertex set in tournaments as fast as without the subset
• Approximate monotone local search for weighted problems
• An FPT algorithm for edge subset feedback edge set
• Graphs without two vertex-disjoint S-cycles

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4507392)