Parameterized complexity of deletion to scattered graph classes

DOI10.4230/LIPICS.IPEC.2020.18MaRDI QIDQ6089665zbMATH OpenFDO

Authors Ashwin Jacob, Diptapriyo Majumdar, Venkatesh Raman

Publication date 13 November 2023

zbMATH Keywords

parameterized complexityimportant separatorsscattered graph classes

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Parameterized complexity, tractability and kernelization (68Q27)

Recommendations

• Deletion to scattered graph classes. I: Case of finite number of graph classes
• Deletion to scattered graph classes. II: Improved FPT algorithms for deletion to pairs of graph classes
• Parameterized complexity of vertex deletion into perfect graph classes
• Parameterized complexity of vertex deletion into perfect graph classes
• FPT algorithms for FVS parameterized by split and cluster vertex deletion sets and other parameters

Cites work

• A Faster FPT Algorithm and a Smaller Kernel for Block Graph Vertex Deletion
• An FPT algorithm for Tree Deletion Set
• An improved parameterized algorithm for the minimum node multiway cut problem
• Bivariate complexity analysis of \textsc{Almost Forest Deletion}
• Discovering archipelagos of tractability for constraint satisfaction and counting
• Faster deterministic \textsc{Feedback Vertex Set}
• Fixed-parameter tractability of graph modification problems for hereditary properties
• Generalized pseudoforest deletion: algorithms and uniform kernel
• Graph Classes: A Survey
• Intersection statements for systems of sets
• Node-Deletion Problems on Bipartite Graphs
• Parameterized algorithms
• Parameterized complexity of vertex deletion into perfect graph classes
• Parameterized graph separation problems
• Parameterized tractability of multiway cut with parity constraints
• Strong parameterized deletion: bipartite graphs
• The node-deletion problem for hereditary properties is NP-complete
• Wheel-Free Deletion Is W[2]-Hard

Cited in

(6)

• Faster FPT algorithms for deletion to pairs of graph classes
• Deletion to scattered graph classes. I: Case of finite number of graph classes
• Single-exponential FPT algorithms for enumerating secluded \(\mathcal{F}\)-free subgraphs and deleting to scattered graph classes
• scientific article; zbMATH DE number 7278081 (Why is no real title available?)
• Deletion to scattered graph classes. II: Improved FPT algorithms for deletion to pairs of graph classes
• Distance from triviality 2.0: hybrid parameterizations

This page was built for publication: Parameterized complexity of deletion to scattered graph classes

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