Generalized Pseudoforest Deletion: Algorithms and Uniform Kernel

DOI10.1137/16M1100794zbMath1384.05148OpenAlexW4239581244WikidataQ129979804 ScholiaQ129979804MaRDI QIDQ4637327

Ashutosh Rai, Saket Saurabh, Geevarghese Philip

Publication date: 18 April 2018

Published in: SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/16m1100794

zbMATH Keywords

parameterized complexityprotrusionsgeneralization of feedback vertex setuniform kernels

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Analysis of algorithms (68W40) Graph theory (including graph drawing) in computer science (68R10) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items (6)

Parameterized orientable deletion ⋮ Deletion to scattered graph classes. I: Case of finite number of graph classes ⋮ Fixed parameterized algorithms for generalized feedback vertex set problems ⋮ Unnamed Item ⋮ Improved FPT Algorithms for Deletion to Forest-Like Structures. ⋮ FPT algorithms for generalized feedback vertex set problems

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Fundamentals of parameterized complexity
• Finding odd cycle transversals.
• Graph minors. XX: Wagner's conjecture
• Compression-based fixed-parameter algorithms for feedback vertex set and edge bipartization
• A cubic kernel for feedback vertex set and loop cutset
• The node-deletion problem for hereditary properties is NP-complete
• Bivariate complexity analysis of \textsc{Almost Forest Deletion}
• A faster parameterized algorithm for pseudoforest deletion
• Faster deterministic \textsc{Feedback Vertex Set}
• Uniform Kernelization Complexity of Hitting Forbidden Minors
• The Undirected Feedback Vertex Set Problem Has a Poly(k) Kernel
• Strong Parameterized Deletion: Bipartite Graphs
• (Meta) Kernelization
• Solving d-SAT via Backdoors to Small Treewidth
• 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

This page was built for publication: Generalized Pseudoforest Deletion: Algorithms and Uniform Kernel