A randomized polynomial kernel for subset feedback vertex set
From MaRDI portal
Publication:1702849
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
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 2 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
