Alambardar Meybodi, Mohsen ;
Fomin, Fedor ;
Mouawad, Amer E. ;
Panolan, Fahad
On the Parameterized Complexity of [1,j]Domination Problems
Abstract
For a graph G, a set D subseteq V(G) is called a [1,j]dominating set if every vertex in V(G) setminus D has at least one and at most j neighbors in D. A set D subseteq V(G) is called a [1,j]total dominating set if every vertex in V(G) has at least one and at most j neighbors in D. In the [1,j](Total) Dominating Set problem we are given a graph G and a positive integer k. The objective is to test whether there exists a [1,j](total) dominating set of size at most k. The [1,j]Dominating Set problem is known to be NPcomplete, even for restricted classes of graphs such as chordal and planar graphs, but polynomialtime solvable on split graphs. The [1,2]Total Dominating Set problem is known to be NPcomplete, even for bipartite graphs. As both problems generalize the Dominating Set problem, both are W[1]hard when parameterized by solution size. In this work, we study [1,j]Dominating Set on sparse graph classes from the perspective of parameterized complexity and prove the following results when the problem is parameterized by solution size:
 [1,j]Dominating Set is W[1]hard on ddegenerate graphs for d = j + 1;
 [1,j]Dominating Set is FPT on nowhere dense graphs.
We also prove that the known algorithm for [1,j]Dominating Set on split graphs is optimal under the Strong Exponential Time Hypothesis (SETH). Finally, assuming SETH, we provide a lower bound for the running time of any algorithm solving the [1,2]Total Dominating Set problem parameterized by pathwidth.
BibTeX  Entry
@InProceedings{alambardarmeybodi_et_al:LIPIcs:2018:9933,
author = {Mohsen Alambardar Meybodi and Fedor Fomin and Amer E. Mouawad and Fahad Panolan},
title = {{On the Parameterized Complexity of [1,j]Domination Problems}},
booktitle = {38th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2018)},
pages = {34:134:14},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959770934},
ISSN = {18688969},
year = {2018},
volume = {122},
editor = {Sumit Ganguly and Paritosh Pandya},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2018/9933},
URN = {urn:nbn:de:0030drops99330},
doi = {10.4230/LIPIcs.FSTTCS.2018.34},
annote = {Keywords: [1, j]dominating set, parameterized complexity, sparse graphs}
}
05.12.2018
Keywords: 

[1, j]dominating set, parameterized complexity, sparse graphs 
Seminar: 

38th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2018)

Issue date: 

2018 
Date of publication: 

05.12.2018 