Tight Complexity Bounds for Counting Generalized Dominating Sets in Bounded-Treewidth Graphs—Part I: Algorithmic Results

We investigate how efficiently a well-studied family of domination-type problems can be solved on bounded-treewidth graphs. For sets \(σ,ρ\) of non-negative integers, a \((σ,ρ)\) -set of a graph G is a set S of vertices such that \(|N(u)∩ S|∈σ\) for every \(u∈ S\) , and \(|N(\!v)∩ S|∈ρ\) for every \(v∈ S\) . The problem of finding a \((σ,ρ)\) -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 \((σ,ρ)\) , we determine (under standard complexity assumptions) the best possible value \(cσ,ρ\) such that there is an algorithm that counts \((σ,ρ)\) -sets in time \(cσ,ρᵗʷ· nO(1)\) (if a tree decomposition of width \(tw\) is given in the input). Let \(s_{{ top}}\) denote the largest element of \(σ\) if \(σ\) is finite, or the largest missing integer \(+1\) if \(σ\) is cofinite; \(r_{{ top}}\) is defined analogously for \(ρ\) . Surprisingly, \(cσ,ρ\) is often significantly smaller than the natural bound \(s_{{ top}}+r_{{ top}}+2\) achieved by existing algorithms. Toward defining \(cσ,ρ\) , we say that \((σ,ρ)\) is \({m}\) -structured if there is a pair \((α,β)\) such that every integer in \(σ\) equals \(α\) mod \({m}\) , and every integer in \(ρ\) equals \(β\) mod \({m}\) . Then, setting — \(cσ,ρ=s_{{ top}}+r_{{ top}}+2\) if \((σ,ρ)\) is not \({m}\) -structured for any \({m}≥ 2\) , — \(cσ,ρ=max\{s_{{ top}},r_{{ top}}\}+2\) if \((σ,ρ)\) is 2-structured, but not \({m}\) -structured for any \({m}≥ 3\) , and <jats:inli