Shining Light on Periodic Dominating Sets in Bounded-Treewidth Graphs
<|reference_start|>Shining Light on Periodic Dominating Sets in Bounded-Treewidth Graphs: For the vertex selection problem $(\sigma,\rho)$-DomSet one is given two fixed sets $\sigma$ and $\rho$ of integers and the task is to decide whether we can select vertices of the input graph, such that, for every selected vertex, the number of selected neighbors is in $\sigma$ and, for every unselected vertex, the number of selected neighbors is in $\rho$. This framework covers Independent Set and Dominating Set for example.   We investigate the case when $\sigma$ and $\rho$ are periodic sets with the same period $m\ge 2$, that is, the sets are two (potentially different) residue classes modulo $m$. We study the problem parameterized by treewidth and present an algorithm that solves in time $m^{tw} \cdot n^{O(1)}$ the decision, minimization and maximization version of the problem. This significantly improves upon the known algorithms where for the case $m \ge 3$ not even an explicit running time is known. We complement our algorithm by providing matching lower bounds which state that there is no $(m-\epsilon)^{pw} \cdot n^{O(1)}$ unless SETH fails. For $m = 2$, we extend these bound to the minimization version as the decision version is efficiently solvable.<|reference_end|>
@article{greilhuber2024shining,
    title={Shining Light on Periodic Dominating Sets in Bounded-Treewidth Graphs},
    author={Jakob Greilhuber and Philipp Schepper and Philip Wellnitz},
    journal={arXiv preprint arXiv:2403.07524},
    year={2024},
    archivePrefix={arXiv},
    eprint={2403.07524},
    primaryClass={cs.DS cs.CC}
}