Deletion to scattered graph classes. I: Case of finite number of graph classes

DOI10.1016/j.jcss.2023.05.005zbMath1529.68215arXiv2105.04660OpenAlexW4380738837MaRDI QIDQ6133645

Ashwin Jacob, Jari J. H. de Kroon, Diptapriyo Majumdar, Venkatesh Raman

Publication date: 21 August 2023

Published in: Journal of Computer and System Sciences (Search for Journal in Brave)

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

zbMATH Keywords

fixed-parameter tractabilityparameterized complexityimportant separatorsscattered graph classes

Mathematics Subject Classification ID

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

Cites Work

• Chordal editing is fixed-parameter tractable
• Parameterized complexity of vertex deletion into perfect graph classes
• Parameterized graph separation problems
• The node-deletion problem for hereditary properties is NP-complete
• Fixed-parameter tractability of graph modification problems for hereditary properties
• Bivariate complexity analysis of \textsc{Almost Forest Deletion}
• Algorithmic graph theory and perfect graphs
• Faster deterministic \textsc{Feedback Vertex Set}
• Faster FPT algorithms for deletion to pairs of graph classes
• An improved parameterized algorithm for the minimum node multiway cut problem
• Treewidth computation and extremal combinatorics
• The monadic second-order logic of graphs. I: Recognizable sets of finite graphs
• FPT algorithms to compute the elimination distance to bipartite graphs and more
• Graph Theory
• Parameterized Tractability of Multiway Cut with Parity Constraints
• Easy problems for tree-decomposable graphs
• Linear Time Parameterized Algorithms for Subset Feedback Vertex Set
• Wheel-Free Deletion Is W[2-Hard]
• Node-Deletion Problems on Bipartite Graphs
• Strong Parameterized Deletion: Bipartite Graphs
• Generalized Pseudoforest Deletion: Algorithms and Uniform Kernel
• Interval Deletion Is Fixed-Parameter Tractable
• Discovering Archipelagos of Tractability for Constraint Satisfaction and Counting
• Reducing CMSO model checking to highly connected graphs
• Saving Critical Nodes with Firefighters is FPT
• Hitting Selected (Odd) Cycles
• Parameterized Algorithms
• Deletion to scattered graph classes. II: Improved FPT algorithms for deletion to pairs of graph classes

This page was built for publication: Deletion to scattered graph classes. I: Case of finite number of graph classes