Shining Light on Periodic Dominating Sets in Bounded-Treewidth Graphs
J Greilhuber, P Schepper, P Wellnitz - arXiv preprint arXiv:2403.07524, 2024 - arxiv.org
J Greilhuber, P Schepper, P Wellnitz
arXiv preprint arXiv:2403.07524, 2024•arxiv.orgFor 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 …
$\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 …
For the vertex selection problem -DomSet one is given two fixed sets and 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 and, for every unselected vertex, the number of selected neighbors is in . This framework covers Independent Set and Dominating Set for example. We investigate the case when and are periodic sets with the same period , that is, the sets are two (potentially different) residue classes modulo . We study the problem parameterized by treewidth and present an algorithm that solves in time the decision, minimization and maximization version of the problem. This significantly improves upon the known algorithms where for the case not even an explicit running time is known. We complement our algorithm by providing matching lower bounds which state that there is no unless SETH fails. For , we extend these bound to the minimization version as the decision version is efficiently solvable.
arxiv.org