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

Treewidth (tw) is an important parameter that, when bounded, yieldstractability for many problems. For example, graph problems expressible inMonadic Second Order (MSO) logic and QUANTIFIED SAT or, more generally,QUANTIFIED CSP, are FPT parameterized by the tw of the input's (primal) graphplus the length of the MSO-formula [Courcelle, Information & Computation 1990]and the quantifier rank [Chen, ECAI 2004], resp. The algorithms from these(meta-)results have running times whose dependence on tw is a tower ofexponents. A conditional lower bound by Fichte et al. [LICS 2020] shows that,for QUANTIFIED SAT, the height of this tower is equal to the number ofquantifier alternations. Lower bounds showing that at least double-exponentialfactors in the running time are necessary are rare: there are very few (for twand vertex cover vc parameterizations) and they are for problems that arecomplete for #NP, $\Sigma_2^p$, $\Pi_2^p$, or higher levels of the polynomialhierarchy.  We show, for the first time, that it is not necessary to go higher up in thepolynomial hierarchy to obtain such lower bounds. We design a novel, yet simpleversatile technique based on Sperner families to obtain such lower bounds andapply it to 3 problems: METRIC DIMENSION, STRONG METRIC DIMENSION, and GEODETICSET. We prove that they do not admit $2^{2^{o(tw)}} \cdot n^{O(1)}$-timealgorithms, even on bounded diameter graphs, unless the ETH fails. For STRONGMETRIC DIMENSION, the lower bound holds even for vc. This is impossible for theother two as they admit $2^{O({vc}^2)} \cdot n^{O(1)}$-time algorithms. We showthat, unless the ETH fails, they do not admit $2^{o({vc}^2)}\cdotn^{O(1)}$-time algorithms, which are also rare results. The lower bounds forthe vc parameterizations also yield rare lower bounds on the vertex-kernelsizes of these problems. We complement our lower bounds with matching upperbounds.

Problems in NP can Admit Double-Exponential Lower Bounds when Parameterized by Treewidth and Vertex Cover