Kanesh, Lawqueen ;
Madathil, Jayakrishnan ;
Roy, Sanjukta ;
Sahu, Abhishek ;
Saurabh, Saket
Further Exploiting cClosure for FPT Algorithms and Kernels for Domination Problems
Abstract
For a positive integer c, a graph G is said to be cclosed if every pair of nonadjacent vertices in G have at most c1 neighbours in common. The closure of a graph G, denoted by cl(G), is the least positive integer c for which G is cclosed. The class of cclosed graphs was introduced by Fox et al. [ICALP `18 and SICOMP `20]. Koana et al. [ESA `20] started the study of using cl(G) as an additional structural parameter to design kernels for problems that are Whard under standard parameterizations. In particular, they studied problems such as Independent Set, Induced Matching, Irredundant Set and (Threshold) Dominating Set, and showed that each of these problems admits a polynomial kernel, either w.r.t. the parameter k+c or w.r.t. the parameter k for each fixed value of c. Here, k is the solution size and c = cl(G). The work of Koana et al. left several questions open, one of which was whether the Perfect Code problem admits a fixedparameter tractable (FPT) algorithm and a polynomial kernel on cclosed graphs. In this paper, among other results, we answer this question in the affirmative. Inspired by the FPT algorithm for Perfect Code, we further explore two more domination problems on the graphs of bounded closure. The other problems that we study are Connected Dominating Set and Partial Dominating Set. We show that Perfect Code and Connected Dominating Set are fixedparameter tractable w.r.t. the parameter k+cl(G), whereas Partial Dominating Set, parameterized by k is W[1]hard even when cl(G) = 2. We also show that for each fixed c, Perfect Code admits a polynomial kernel on the class of cclosed graphs. And we observe that Connected Dominating Set has no polynomial kernel even on 2closed graphs, unless NP ⊆ coNP/poly.
BibTeX  Entry
@InProceedings{kanesh_et_al:LIPIcs.STACS.2022.39,
author = {Kanesh, Lawqueen and Madathil, Jayakrishnan and Roy, Sanjukta and Sahu, Abhishek and Saurabh, Saket},
title = {{Further Exploiting cClosure for FPT Algorithms and Kernels for Domination Problems}},
booktitle = {39th International Symposium on Theoretical Aspects of Computer Science (STACS 2022)},
pages = {39:139:20},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959772228},
ISSN = {18688969},
year = {2022},
volume = {219},
editor = {Berenbrink, Petra and Monmege, Benjamin},
publisher = {Schloss Dagstuhl  LeibnizZentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2022/15849},
URN = {urn:nbn:de:0030drops158494},
doi = {10.4230/LIPIcs.STACS.2022.39},
annote = {Keywords: cclosed graphs, domination problems, perfect code, connected dominating set, fixedparameter tractable, polynomial kernel}
}
09.03.2022
Keywords: 

cclosed graphs, domination problems, perfect code, connected dominating set, fixedparameter tractable, polynomial kernel 
Seminar: 

39th International Symposium on Theoretical Aspects of Computer Science (STACS 2022)

Issue date: 

2022 
Date of publication: 

09.03.2022 