Shining Light on Periodic Dominating Sets in Bounded-Treewidth Graphs

Abstract

Given a graph G, a set S ⊆ V (G) is a (σ, ρ)-set of G if and only if • for all v ∈ S we have |N (v) ∩ S| ∈ σ, and • for all v ∉ S we have |N (v) ∩ S| ∈ ρ. The problem of deciding whether a graph has a (σ, ρ)-set is the decision problem of (σ, ρ)-GenDomSet. Naturally, one can also consider the minimization and maximization problems, in which S is supposed to be as small, respectively as large as possible. The framework of (σ, ρ)-GenDomSet captures numerous classical graph problems. For instance, the problem corresponds to Dominating Set when σ = N and ρ = N \ {0}, and we obtain Independent Set by setting σ = {0}, ρ = N. In this thesis, the work by Focke et al. [SODA 2023] is extended for the case where σ and ρ are periodic sets, specifically residue classes modulo m. We show that when 0 ∉ ρ and m ≥ 3, for any ε > 0, the decision problem cannot be solved in time (m − ε)^tw · |G|^O(1), even when the input graph is provided together with a tree decomposition of width tw, unless the Strong Exponential Time Hypothesis is false. If m = 2, the decision problem can be solved in polynomial time. For this case, we extend the lower bound to the minimization problem assuming 0 ∉ ρ, and the maximization problem in all settings. In all cases, the obtained lower bounds are tight, as one can solve the decision problem and both optimization problems in time m^tw · |G|^O(1). The work in this thesis represents the first work that provides tight conditional lower bounds for (σ, ρ)-GenDomSet parameterized by treewidth when σ, ρ are neither finite nor cofinite, making it a first step into this domain. Large parts of this work were done during a summer internship at the Max Planck Institute of informatics supervised by Philip Wellnitz and Philipp Schepper.