Shining Light on Periodic Dominating Sets in Bounded-Treewidth Graphs

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 m≥ 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ᵗʷ · nO(1) the decision, minimization and maximization version of the problem. This significantly improves upon the known algorithms where for the case m ≥ 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-ε)ᵖʷ · nO(1) unless SETH fails. For $m = 2$, we extend these bound to the minimization version as the decision version is efficiently solvable.