Deletion to scattered graph classes. I: Case of finite number of graph classes
From MaRDI portal
Publication:6133645
DOI10.1016/J.JCSS.2023.05.005zbMATH Open1529.68215arXiv2105.04660OpenAlexW4380738837MaRDI QIDQ6133645FDOQ6133645
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)
Abstract: Graph-modification problems, where we modify a graph by adding or deleting vertices or edges or contracting edges to obtain a graph in a {it simpler} class, is a well-studied optimization problem in all algorithmic paradigms including classical, approximation and parameterized complexity. Specifically, graph-deletion problems, where one needs to delete a small number of vertices to make the resulting graph to belong to a given non-trivial hereditary graph class, captures several well-studied problems including {sc Vertex Cover}, {sc Feedback Vertex Set}, {sc Odd Cycle Transveral}, {sc Cluster Vertex Deletion}, and {sc Perfect Deletion}. Investigation into these problems in parameterized complexity has given rise to powerful tools and techniques. We initiate a study of a natural variation of the problem of deletion to {it scattered graph classes}. We want to delete at most vertices so that in the resulting graph, each connected component belongs to one of a constant number of graph classes. As our main result, we show that this problem is fixed-parameter tractable (FPT) when the deletion problem corresponding to each of the finite number of graph classes is known to be FPT and the properties that a graph belongs to any of the classes is expressible in Counting Monodic Second Order (CMSO) logic. While this is shown using some black box theorems in parameterized complexity, we give a faster FPT algorithm when each of the graph classes has a finite forbidden set.
Full work available at URL: https://arxiv.org/abs/2105.04660
Graph theory (including graph drawing) in computer science (68R10) Parameterized complexity, tractability and kernelization (68Q27)
Cites Work
- Treewidth computation and extremal combinatorics
- Fixed-parameter tractability of graph modification problems for hereditary properties
- The node-deletion problem for hereditary properties is NP-complete
- Algorithmic graph theory and perfect graphs
- The monadic second-order logic of graphs. I: Recognizable sets of finite graphs
- Easy problems for tree-decomposable graphs
- Parameterized Algorithms
- Parameterized graph separation problems
- Node-Deletion Problems on Bipartite Graphs
- An improved parameterized algorithm for the minimum node multiway cut problem
- Graph Theory
- Chordal editing is fixed-parameter tractable
- Faster deterministic \textsc{Feedback Vertex Set}
- Interval Deletion Is Fixed-Parameter Tractable
- Parameterized complexity of vertex deletion into perfect graph classes
- Parameterized Tractability of Multiway Cut with Parity Constraints
- Linear Time Parameterized Algorithms for Subset Feedback Vertex Set
- Discovering Archipelagos of Tractability for Constraint Satisfaction and Counting
- Wheel-Free Deletion Is W[2]-Hard
- Bivariate complexity analysis of \textsc{Almost Forest Deletion}
- Reducing CMSO model checking to highly connected graphs
- Generalized Pseudoforest Deletion: Algorithms and Uniform Kernel
- Faster FPT algorithms for deletion to pairs of graph classes
- FPT algorithms to compute the elimination distance to bipartite graphs and more
- Deletion to scattered graph classes. II: Improved FPT algorithms for deletion to pairs of graph classes
- Hitting Selected (Odd) Cycles
- Strong Parameterized Deletion: Bipartite Graphs
- Saving Critical Nodes with Firefighters is FPT
Cited In (2)
This page was built for publication: Deletion to scattered graph classes. I: Case of finite number of graph classes
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6133645)
