License: 
Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.IPEC.2020.18
URN: urn:nbn:de:0030-drops-133210
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2020/13321/
Jacob, Ashwin ;
Majumdar, Diptapriyo ;
Raman, Venkatesh
Parameterized Complexity of Deletion to Scattered Graph Classes
Abstract
Graph-modification 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 well-studied optimization problem in all algorithmic paradigms including classical, approximation and parameterized complexity. Specifically, graph-deletion problems, where one needs to delete at most k vertices to place it in a given non-trivial hereditary (closed under induced subgraphs) graph class, captures several well-studied 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 fixed-parameter 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 fixed-parameter tractable by a O^*(2^(k^O(1))) algorithm, using a combination of the well-known 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:1--18:17},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-172-6},
ISSN = {1868-8969},
year = {2020},
volume = {180},
editor = {Yixin Cao and Marcin Pilipczuk},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2020/13321},
URN = {urn:nbn:de:0030-drops-133210},
doi = {10.4230/LIPIcs.IPEC.2020.18},
annote = {Keywords: Parameterized Complexity, Scattered Graph Classes, Important Separators}
}
|
Keywords: |
|
Parameterized Complexity, Scattered Graph Classes, Important Separators |
|
Collection: |
|
15th International Symposium on Parameterized and Exact Computation (IPEC 2020) |
|
Issue Date: |
|
2020 |
|
Date of publication: |
|
04.12.2020 |
