English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

For a well-studied family of domination-type problems, in bounded-treewidthgraphs, we investigate whether it is possible to find faster algorithms. Forsets $\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\inS$, and $|N(v)\cap S|\in \rho$ for every $v\not\in S$. The problem of finding a$(\sigma,\rho)$-set (of a certain size) unifies common problems like$\text{Independent Set}$, $\text{Dominating Set}$, $\text{IndependentDominating Set}$, and many others.  In an accompanying paper, it is proven that, for all pairs of finite orcofinite sets $(\sigma,\rho)$, there is an algorithm that counts$(\sigma,\rho)$-sets in time $(c_{\sigma,\rho})^{\text{tw}}\cdot n^{O(1)}$ (ifa tree decomposition of width $\text{tw}$ is given in the input). Here,$c_{\sigma,\rho}$ is a constant with an intricate dependency on $\sigma$ and$\rho$. Despite this intricacy, we show that the algorithms in the accompanyingpaper are most likely optimal, i.e., for any pair $(\sigma, \rho)$ of finite orcofinite sets where the problem is non-trivial, and any $\varepsilon>0$, a$(c_{\sigma,\rho}-\varepsilon)^{\text{tw}}\cdot n^{O(1)}$-algorithm countingthe number of $(\sigma,\rho)$-sets would violate the Counting StrongExponential-Time Hypothesis ($\#$SETH). For finite sets $\sigma$ and $\rho$,our lower bounds also extend to the decision version, showing that thosealgorithms are optimal in this setting as well.

Tight Complexity Bounds for Counting Generalized Dominating Sets in Bounded-Treewidth Graphs Part II: Hardness Results