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

For all pairs of finite or cofinite sets (σ,ρ), we determine (under standard complexity assumptions) the best possible value c_{σ,ρ} to count (σ,ρ)-sets in time O*(c_{σ,ρ}^tw) (if a tree decomposition of width tw is given in the input). Surprisingly, c_{σ,ρ} is often significantly smaller than the natural bound achieved by existing algorithms [van Rooij, 2020]. For example, for the Perfect Code problem (σ={0}, ρ={1}), this improves the O*(3^tw) algorithm to O*(2^tw).

We show that our algorithms are most likely optimal, i.e., for any (non-trivial) pair (σ,ρ) of finite or cofinite sets, and any ε>0, a O*((c_{σ,ρ}-ε)^tw)-algorithm counting the number of (σ,ρ)-sets would violate #SETH. For finite sets σ and ρ, 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.

Joint work with: Jacob Focke, Dániel Marx, Fionn Mc Inerney, Daniel Neuen, Govind S. Sankar, and Philip Wellnitz