cispa_all_3805.pdf (1.8 MB)

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

conference contribution

posted on 2023-11-29, 18:25 authored by Jacob FockeJacob Focke, Dániel MarxDániel Marx, Fionn Mc Inerney, Daniel Neuen, Govind Sankar, Philipp SchepperPhilipp Schepper, Philip WellnitzWe 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

ot\in S$. The problem of finding a $(\sigma,\rho)$-set (of a certain size) unifies standard problems such as \textsc{Independent Set}, \textsc{Dominating Set}, \textsc{Independent Dominating Set}, and many others. For almost 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}^\tw\cdot n^{\O(1)}$ (if a tree decomposition of width $\tw$ is given in the input). Let $\sigMax$ denote the largest element of $\sigma$ if $\sigma$ is finite, or the largest missing integer $+1$ if $\sigma$ is cofinite; $\rhoMax$ is defined analogously for $\rho$. Surprisingly, $c_{\sigma,\rho}$ is often significantly smaller than the natural bound $\sigMax+\rhoMax+2$ achieved by existing algorithms [van Rooij, 2020]. Toward defining $c_{\sigma,\rho}$, we say that $(\sigma, \rho)$ is $\mname$-structured if there is a pair $(\alpha,\beta)$ such that every integer in $\sigma$ equals $\alpha$ mod $\mname$, and every integer in $\rho$ equals $\beta$ mod $\mname$. Then, setting \begin{itemize} \item $c_{\sigma,\rho}=\max\{\sigMax,\rhoMax\}+1$ if $(\sigma,\rho)$ is $\mname$-structured for some $\mname \ge 3$, or 2-structured with $\sigMax

eq \rhoMax$, or 2-structured with $\sigMax=\rhoMax$ being odd, \item $c_{\sigma,\rho}=\max\{\sigMax,\rhoMax\}+2$ if $(\sigma,\rho)$ is 2-structured, but not $\mname$-structured for any $\mname \ge 3$, and $\sigMax=\rhoMax$ is even, and \item $c_{\sigma,\rho}=\sigMax+\rhoMax+2$ if $(\sigma,\rho)$ is not $\mname$-structured for any $\mname\ge 2$, \end{itemize} we provide algorithms counting $(\sigma,\rho)$-sets in time $c_{\sigma,\rho}^\tw\cdot n^{\O(1)}$. For example, for the \textsc{Exact Independent Dominating Set} problem (also known as \textsc{Perfect Code}) corresponding to $\sigma=\{0\}$ and $\rho=\{1\}$, this improves the $3^\tw\cdot n^{\O(1)}$ algorithm of van Rooij to $2^\tw\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 (except those having cofinite $\sigma$ with $\rho=\mathbb Z_{\ge0}$), and any $\varepsilon>0$, a $(c_{\sigma,\rho}-\varepsilon)^\tw\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.

ot\in S$. The problem of finding a $(\sigma,\rho)$-set (of a certain size) unifies standard problems such as \textsc{Independent Set}, \textsc{Dominating Set}, \textsc{Independent Dominating Set}, and many others. For almost 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}^\tw\cdot n^{\O(1)}$ (if a tree decomposition of width $\tw$ is given in the input). Let $\sigMax$ denote the largest element of $\sigma$ if $\sigma$ is finite, or the largest missing integer $+1$ if $\sigma$ is cofinite; $\rhoMax$ is defined analogously for $\rho$. Surprisingly, $c_{\sigma,\rho}$ is often significantly smaller than the natural bound $\sigMax+\rhoMax+2$ achieved by existing algorithms [van Rooij, 2020]. Toward defining $c_{\sigma,\rho}$, we say that $(\sigma, \rho)$ is $\mname$-structured if there is a pair $(\alpha,\beta)$ such that every integer in $\sigma$ equals $\alpha$ mod $\mname$, and every integer in $\rho$ equals $\beta$ mod $\mname$. Then, setting \begin{itemize} \item $c_{\sigma,\rho}=\max\{\sigMax,\rhoMax\}+1$ if $(\sigma,\rho)$ is $\mname$-structured for some $\mname \ge 3$, or 2-structured with $\sigMax

eq \rhoMax$, or 2-structured with $\sigMax=\rhoMax$ being odd, \item $c_{\sigma,\rho}=\max\{\sigMax,\rhoMax\}+2$ if $(\sigma,\rho)$ is 2-structured, but not $\mname$-structured for any $\mname \ge 3$, and $\sigMax=\rhoMax$ is even, and \item $c_{\sigma,\rho}=\sigMax+\rhoMax+2$ if $(\sigma,\rho)$ is not $\mname$-structured for any $\mname\ge 2$, \end{itemize} we provide algorithms counting $(\sigma,\rho)$-sets in time $c_{\sigma,\rho}^\tw\cdot n^{\O(1)}$. For example, for the \textsc{Exact Independent Dominating Set} problem (also known as \textsc{Perfect Code}) corresponding to $\sigma=\{0\}$ and $\rho=\{1\}$, this improves the $3^\tw\cdot n^{\O(1)}$ algorithm of van Rooij to $2^\tw\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 (except those having cofinite $\sigma$ with $\rho=\mathbb Z_{\ge0}$), and any $\varepsilon>0$, a $(c_{\sigma,\rho}-\varepsilon)^\tw\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.

## History

## Preferred Citation

Jacob Focke, Dániel Marx, Inerney Mc, Daniel Neuen, Govind Sankar, Philipp Schepper and Philip Wellnitz. Tight Complexity Bounds for Counting Generalized Dominating Sets in Bounded-Treewidth Graphs. In: ACM-SIAM Symposium on Discrete Algorithms (SODA). 2023.## Primary Research Area

- Algorithmic Foundations and Cryptography

## Name of Conference

ACM-SIAM Symposium on Discrete Algorithms (SODA)## Legacy Posted Date

2022-10-12## Open Access Type

- Green

## BibTeX

@inproceedings{cispa_all_3805, title = "Tight Complexity Bounds for Counting Generalized Dominating Sets in Bounded-Treewidth Graphs", author = "Focke, Jacob and Marx, Dániel and Mc Inerney, Fionn and Neuen, Daniel and Sankar, Govind and Schepper, Philipp and Wellnitz, Philip", booktitle="{ACM-SIAM Symposium on Discrete Algorithms (SODA)}", year="2023", }## Usage metrics

## Categories

No categories selected## Licence

## Exports

RefWorks

BibTeX

Ref. manager

Endnote

DataCite

NLM

DC