License: 
Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.STACS.2022.39
URN: urn:nbn:de:0030-drops-158494
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2022/15849/
Kanesh, Lawqueen ;
Madathil, Jayakrishnan ;
Roy, Sanjukta ;
Sahu, Abhishek ;
Saurabh, Saket
Further Exploiting c-Closure for FPT Algorithms and Kernels for Domination Problems
Abstract
For a positive integer c, a graph G is said to be c-closed if every pair of non-adjacent vertices in G have at most c-1 neighbours in common. The closure of a graph G, denoted by cl(G), is the least positive integer c for which G is c-closed. The class of c-closed 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 W-hard 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 fixed-parameter tractable (FPT) algorithm and a polynomial kernel on c-closed 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 fixed-parameter 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 c-closed graphs. And we observe that Connected Dominating Set has no polynomial kernel even on 2-closed graphs, unless NP ⊆ co-NP/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 c-Closure for FPT Algorithms and Kernels for Domination Problems}},
booktitle = {39th International Symposium on Theoretical Aspects of Computer Science (STACS 2022)},
pages = {39:1--39:20},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-222-8},
ISSN = {1868-8969},
year = {2022},
volume = {219},
editor = {Berenbrink, Petra and Monmege, Benjamin},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2022/15849},
URN = {urn:nbn:de:0030-drops-158494},
doi = {10.4230/LIPIcs.STACS.2022.39},
annote = {Keywords: c-closed graphs, domination problems, perfect code, connected dominating set, fixed-parameter tractable, polynomial kernel}
}
|
Keywords: |
|
c-closed graphs, domination problems, perfect code, connected dominating set, fixed-parameter tractable, polynomial kernel |
|
Collection: |
|
39th International Symposium on Theoretical Aspects of Computer Science (STACS 2022) |
|
Issue Date: |
|
2022 |
|
Date of publication: |
|
09.03.2022 |
