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.
Categories: cs.DS