We investigate how efficiently a well-studied family of domination-type
problems can be solved on bounded-treewidth graphs. For sets $\sigma ,\rho $ of
non-negative integers, a $(\sigma ,\rho )$ -set of a graph $G$ is a set $S$ of
vertices such that $|N(u)\cap S|\in \sigma $ for every $u\in S$ , and $|N(v)\cap S|\in \rho $ for every $v\notin S$ . The problem of finding a
$(\sigma ,\rho )$ -set (of a certain size) unifies standard problems such as
Independent Set, Dominating Set, Independent Dominating Set, and many others.
For all pairs of finite or cofinite sets $(\sigma ,\rho )$ , we determine (under
standard complexity assumptions) the best possible value ${c}_{\sigma ,\rho}$ such
that there is an algorithm that counts $(\sigma ,\rho )$ -sets in time
${c}_{\sigma ,\rho}^{\mathsf{t}\mathsf{w}}\cdot {n}^{O(1)}$ (if a tree decomposition of width
$\mathsf{t}\mathsf{w}$ is given in the input). For example, for the Exact Independent
Dominating Set problem (also known as Perfect Code) corresponding to
$\sigma =\{0\}$ and $\rho =\{1\}$ , we improve the ${3}^{\mathsf{t}\mathsf{w}}\cdot {n}^{O(1)}$
algorithm of [van Rooij, 2020] to ${2}^{\mathsf{t}\mathsf{w}}\cdot {n}^{O(1)}$ .
Despite the unusually delicate definition of ${c}_{\sigma ,\rho}$ , we show that
our algorithms are most likely optimal, i.e., for any pair $(\sigma ,\rho )$ of
finite or cofinite sets where the problem is non-trivial, and any
$\epsilon >0$ , a $({c}_{\sigma ,\rho}-\epsilon {)}^{\mathsf{t}\mathsf{w}}\cdot {n}^{O(1)}$ -algorithm counting the number of $(\sigma ,\rho )$ -sets would violate
the Counting Strong Exponential-Time Hypothesis (#SETH). For finite sets
$\sigma $ and $\rho $ , our lower bounds also extend to the decision version,
showing that our algorithms are optimal in this setting as well. In contrast,
for many cofinite sets, we show that further significant improvements for the
decision and optimization versions are possible using the technique of
representative sets.

PREPRINT

# Tight Complexity Bounds for Counting Generalized Dominating Sets in Bounded-Treewidth Graphs

Jacob Focke, Dániel Marx, Fionn Mc Inerney, Daniel Neuen, Govind S. Sankar, Philipp Schepper, Philip Wellnitz

Submitted on 8 November 2022

## Abstract

## Preprint

Subjects: Computer Science - Computational Complexity; Computer Science - Data Structures and Algorithms