2021/05/10 by Ashwin Jacob, Jari J. H. de Kroon, Jacob, Ashwin +5 · 1 citation
Computer Science · #Computability, Logic, AI Algorithms #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences
paper · pdf · doi:10.48550/arxiv.2105.04660
openalex publication_date 2021/05/10 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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.