2026-07-22T13:11:26Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:9933 2024-03-06T10:45:08Z ddc:004 open_access

On the Parameterized Complexity of [1,j]-Domination Problems Alambardar Meybodi, Mohsen Fomin, Fedor Mouawad, Amer E. Panolan, Fahad [1 j]-dominating set parameterized complexity sparse graphs 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 NP-complete, even for restricted classes of graphs such as chordal and planar graphs, but polynomial-time solvable on split graphs. The [1,2]-Total Dominating Set problem is known to be NP-complete, 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 d-degenerate 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Mohsen Alambardar Meybodi and Fedor Fomin and Amer E. Mouawad and Fahad Panolan 2018 Is Part Of LIPIcs, Volume 122, 38th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2018) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.FSTTCS.2018.34 urn:nbn:de:0030-drops-99330 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2018.34 eng https://creativecommons.org/licenses/by/3.0/legalcode