A randomized polynomial kernel for subset feedback vertex set

DOI10.1007/s00224-017-9805-6zbMath1387.68134arXiv1512.02510OpenAlexW2963832031MaRDI QIDQ1702849

Stefan Kratsch, Eva-Maria C. Hols

Publication date: 1 March 2018

Published in: Theory of Computing Systems (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1512.02510

zbMATH Keywords

parameterized complexitykernelizationsubset feedback vertex set

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Randomized algorithms (68W20)

Related Items

Computing a minimum subset feedback vertex set on chordal graphs parameterized by leafage ⋮ 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 ⋮ Parameterized algorithms for Max Colorable Induced Subgraph problem on perfect graphs ⋮ Computing a minimum subset feedback vertex set on chordal graphs parameterized by leafage ⋮ Computing subset transversals in \(H\)-free graphs ⋮ Subset feedback vertex set in chordal and split graphs ⋮ Subset feedback vertex set on graphs of bounded independent set size ⋮ Node multiway cut and subset feedback vertex set on graphs of bounded mim-width

Cites Work

• Unnamed Item
• Unnamed Item
• Fixed-parameter tractability for the subset feedback set problem and the \(S\)-cycle packing problem
• Finding odd cycle transversals.
• A parameterized view on matroid optimization problems
• Matroid matching and some applications
• A short proof of Mader's \(\mathcal S\)-paths theorem
• Faster deterministic \textsc{Feedback Vertex Set}
• Applications of Menger's graph theorem
• A 4 k ² kernel for feedback vertex set
• Finding small separators in linear time via treewidth reduction
• Subset Feedback Vertex Set Is Fixed-Parameter Tractable
• Linear Time Parameterized Algorithms for Subset Feedback Vertex Set
• The Undirected Feedback Vertex Set Problem Has a Poly(k) Kernel
• Approximating Minimum Subset Feedback Sets in Undirected Graphs with Applications
• An 8-Approximation Algorithm for the Subset Feedback Vertex Set Problem
• Representative Sets and Irrelevant Vertices
• Efficient Computation of Representative Sets with Applications in Parameterized and Exact Algorithms
• Half-integrality, LP-branching and FPT Algorithms
• Solving Connectivity Problems Parameterized by Treewidth in Single Exponential Time
• Satisfiability Allows No Nontrivial Sparsification unless the Polynomial-Time Hierarchy Collapses
• Maximum-Minimum Sätze und verallgemeinerte Faktoren von Graphen