Jacob, Ashwin ;
Majumdar, Diptapriyo ;
Raman, Venkatesh
Parameterized Complexity of Deletion to Scattered Graph Classes
Abstract
Graphmodification problems, where we add/delete a small number of vertices/edges to make the given graph to belong to a simpler graph class, is a wellstudied optimization problem in all algorithmic paradigms including classical, approximation and parameterized complexity. Specifically, graphdeletion problems, where one needs to delete at most k vertices to place it in a given nontrivial hereditary (closed under induced subgraphs) graph class, captures several wellstudied problems including Vertex Cover, Feedback Vertex Set, Odd Cycle Transveral, Cluster Vertex Deletion, and Perfect Deletion. Investigation into these problems in parameterized complexity has given rise to powerful tools and techniques. While a precise characterization of the graph classes for which the problem is fixedparameter tractable (FPT) is elusive, it has long been known that if the graph class is characterized by a finite set of forbidden graphs, then the problem is FPT.
In this paper, we initiate a study of a natural variation of the problem of deletion to scattered graph classes where we need 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. A simple hitting set based approach is no longer feasible even if each of the graph classes is characterized by finite forbidden sets. As our main result, we show that this problem (in the case where each graph class has a finite forbidden set) is fixedparameter tractable by a O^*(2^(k^O(1))) algorithm, using a combination of the wellknown techniques in parameterized complexity  iterative compression and important separators. Our approach follows closely that of a related problem in the context of satisfiability [Ganian, Ramanujan, Szeider, TAlg 2017], where one wants to find a small backdoor set so that the resulting CSP (constraint satisfaction problem) instance belongs to one of several easy instances of satisfiability. While we follow the main idea from this work, there are some challenges for our problem which we needed to overcome.
When there are two graph classes with finite forbidden sets to get to, and if one of the forbidden sets has a path, then we show that the problem has a (better) singly exponential algorithm and a polynomial sized kernel. We also design an efficient FPT algorithm for a special case when one of the graph classes has an infinite forbidden set. Specifically, we give a O^*(4^k) algorithm to determine whether k vertices can be deleted from a given graph so that in the resulting graph, each connected component is a tree (the sparsest connected graph) or a clique (the densest connected graph).
BibTeX  Entry
@InProceedings{jacob_et_al:LIPIcs:2020:13321,
author = {Ashwin Jacob and Diptapriyo Majumdar and Venkatesh Raman},
title = {{Parameterized Complexity of Deletion to Scattered Graph Classes}},
booktitle = {15th International Symposium on Parameterized and Exact Computation (IPEC 2020)},
pages = {18:118:17},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959771726},
ISSN = {18688969},
year = {2020},
volume = {180},
editor = {Yixin Cao and Marcin Pilipczuk},
publisher = {Schloss DagstuhlLeibnizZentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2020/13321},
URN = {urn:nbn:de:0030drops133210},
doi = {10.4230/LIPIcs.IPEC.2020.18},
annote = {Keywords: Parameterized Complexity, Scattered Graph Classes, Important Separators}
}
04.12.2020
Keywords: 

Parameterized Complexity, Scattered Graph Classes, Important Separators 
Seminar: 

15th International Symposium on Parameterized and Exact Computation (IPEC 2020)

Issue date: 

2020 
Date of publication: 

04.12.2020 