论文标题
在界限图中计算广义主导集的紧密复杂性界限第I部分：算法结果
Tight Complexity Bounds for Counting Generalized Dominating Sets in Bounded-Treewidth Graphs Part I: Algorithmic Results
论文作者
论文摘要
我们研究了如何在有限的树形图上解决一个有效的统治型问题家族。对于集合$σ，非负整数的ρ$，图$ g $的$（σ，ρ）$是$ | n（u）\ cap s | \ in c s $ in s $中的$ | n（u）\ cap s | \ in s $ in s $，and $ | n（v）\ cap s | for s $ρ$ c的$ s |找到$（σ，ρ）$ - 集合（一定大小）的问题统一了标准问题，例如独立集，主导集，独立统治集和许多其他问题。 对于所有有限或富有货币对$（σ，ρ）$的设置，我们确定（在标准复杂性假设下）最佳值$ c_ {σ，ρ} $，因此有一个算法计数$（σ，ρ）$在时间$ c_ {σ，ρ宽度$ {\ sf tw} $的树分解在输入中给出。例如，对于确切的独立主导集问题（也称为完美代码），对应于$σ= \ {0 \} $和$ρ= \ {1 \ {1 \} $，我们改进了$ 3^{\ sf tw} \ sf tw} \ cdot n^{o（1）} $ n^{o（1）} $。 尽管对$ c_ {σ，ρ} $的定义异常微妙，但随附的论文表明，我们的算法很可能是最佳的，也就是说，对于任何一对$ $（σ，ρ）$的有限或cofinite套件，问题是非琐事的，并且任何$ \ varepsilon> 0 $， $（c_ {σ，ρ} - \ varepsilon）^{\ sf tw} \ cdot n^{o（1）} $ - 计算$（σ，ρ）$的数量的算法会违反计数countent countent countent of Countential Expuroptimal-time Pimental Pimenthess Mathessis（＃SETH）。对于有限的集合$σ$和$ρ$，这些下限也扩展到决策版本，因此，我们的算法在此设置中也是最佳的。相比之下，对于许多辅助集合，我们表明，使用代表性集合的技术可以为决策和优化版本进行进一步的重大改进。
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)\cap S|\in σ$ for every $u\in S$, and $|N(v)\cap S|\in ρ$ for every $v\not\in 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_{σ,ρ}^{\sf tw}\cdot n^{O(1)}$ (if a tree decomposition of width ${\sf tw}$ is given in the input). For example, for the Exact Independent Dominating Set problem (also known as Perfect Code) corresponding to $σ=\{0\}$ and $ρ=\{1\}$, we improve the $3^{\sf tw}\cdot n^{O(1)}$ algorithm of [van Rooij, 2020] to $2^{\sf tw}\cdot n^{O(1)}$. Despite the unusually delicate definition of $c_{σ,ρ}$, an accompanying paper shows that our algorithms are most likely optimal, that is, for any pair $(σ, ρ)$ of finite or cofinite sets where the problem is non-trivial, and any $\varepsilon>0$, a $(c_{σ,ρ}-\varepsilon)^{\sf tw}\cdot n^{O(1)}$-algorithm counting the number of $(σ,ρ)$-sets would violate the Counting Strong Exponential-Time Hypothesis (#SETH). For finite sets $σ$ and $ρ$, these lower bounds also extend to the decision version, and hence, 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.
