@online{Greilhuber2403.07524,
TITLE = {Shining Light on Periodic Dominating Sets in Bounded-Treewidth Graphs},
AUTHOR = {Greilhuber, Jakob and Schepper, Philipp and Wellnitz, Philip},
LANGUAGE = {eng},
URL = {https://arxiv.org/abs/2403.07524},
EPRINT = {2403.07524},
EPRINTTYPE = {arXiv},
YEAR = {2024},
MARGINALMARK = {$\bullet$},
ABSTRACT = {For the vertex selection problem $(\sigma,\rho)$-DomSet one is given two<br>fixed sets $\sigma$ and $\rho$ of integers and the task is to decide whether we<br>can select vertices of the input graph, such that, for every selected vertex,<br>the number of selected neighbors is in $\sigma$ and, for every unselected<br>vertex, the number of selected neighbors is in $\rho$. This framework covers<br>Independent Set and Dominating Set for example.<br> We investigate the case when $\sigma$ and $\rho$ are periodic sets with the<br>same period $m\ge 2$, that is, the sets are two (potentially different) residue<br>classes modulo $m$. We study the problem parameterized by treewidth and present<br>an algorithm that solves in time $m^{tw} \cdot n^{O(1)}$ the decision,<br>minimization and maximization version of the problem. This significantly<br>improves upon the known algorithms where for the case $m \ge 3$ not even an<br>explicit running time is known. We complement our algorithm by providing<br>matching lower bounds which state that there is no $(m-\epsilon)^{pw} \cdot<br>n^{O(1)}$ unless SETH fails. For $m = 2$, we extend these bound to the<br>minimization version as the decision version is efficiently solvable.<br>},
}