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

DOI10.1016/J.JCSS.2023.05.005zbMATH Open1529.68215arXiv2105.04660OpenAlexW4380738837MaRDI QIDQ6133645FDOQ6133645

Authors: 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 $k$ 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

Recommendations

• Parameterized complexity of deletion to scattered 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
• Parameterized vertex deletion problems for hereditary graph classes with a block property

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

• 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 (3)

• Deletion to scattered graph classes. II: Improved FPT algorithms for deletion to pairs of graph classes
• Parameterized complexity of deletion to scattered graph classes
• Single-exponential FPT algorithms for enumerating secluded \(\mathcal{F}\)-free subgraphs and deleting to scattered graph classes

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)