The Price of Being Partial: Complexity of Partial Generalized Dominating Set on Bounded-Treewidth Graphs

The $(σ, ρ)$-domination framework introduced by Telle [Nord. J. Comput.'94] captures many classical graph problems. For fixed sets $σ, ρ$ of non-negative integers, a $(σ,ρ)$-set of a graph $G$ is a set $S$ such that for every $v\in V(G)$, we have (1) if $v \in S$, then $|N(v) \cap S| \in σ$, and (2) if $v \not\in S$, then $|N(v) \cap S| \in ρ$. We initiate the study of a natural partial variant of the problem, in which the constraints given by $σ, ρ$ need not be fulfilled for all vertices, but we want to maximize the number of vertices that are happy in the sense that they satisfy (1) or (2) above. Given a graph $G$ and integers $k$ and $\ell$, the task of $(σ,ρ)$-MinParDomSet is to decide whether there is a set $S \subseteq V(G)$ of size at most $k$ such that at most $\ell$ vertices of the graph are not happy under $S$. We consider the problem on graphs of bounded treewidth for nonempty finite or simple cofinite sets $σ$ and $ρ$, and give matching upper and lower bounds for every such fixed $σ$ and $ρ$ (under the Primal Pathwidth Strong Exponential Time Hypothesis). Let $s_σ^\textsf{p} = \max σ+ 1$ when $σ$ is finite, and $\min σ$ when $σ$ is simple cofinite; define $s_ρ^{\textsf{p}}$ similarly for $ρ$. We show that the problem $(σ,ρ)$-MinParDomSet (1) can be solved in time $(s_σ^\textsf{p} + s_ρ^{\textsf{p}} + 2)^{tw} \cdot |G|^{O(1)}$, when a tree decomposition of width $tw$ is provided together with the input, and (2) for any $\varepsilon>0$, no algorithm can exist that solves the problem in time $(s_σ^\textsf{p} + s_ρ^{\textsf{p}} + 2 - \varepsilon)^{pw} \cdot |G|^{O(1)}$, even when a path decomposition of width $pw$ is provided together with the input.