posted on 2024-07-25, 12:39authored byFlorent Foucaud, Esther Galby, Liana Khazaliya, Shaohua Li, Fionn Mc Inerney, Roohani Sharma, Prafullkumar Tale
Treewidth serves as an important parameter that, when bounded, yields tractability for a wide class of problems. For example, graph problems expressible in Monadic Second Order (MSO) logic and Quantified SAT or, more generally, Quantified CSP, are fixed-parameter tractable parameterized by the treewidth {of the input’s (primal) graph} plus the length of the MSO-formula [Courcelle, Information & Computation 1990] and the quantifier rank [Chen, ECAI 2004], respectively. The algorithms generated by these (meta-)results have running times whose dependence on treewidth is a tower of exponents. A conditional lower bound by Fichte, Hecher, and Pfandler [LICS 2020] shows that, for Quantified SAT, the height of this tower is equal to the number of quantifier alternations. These types of lower bounds, which show that at least double-exponential factors in the running time are necessary, exhibit the extraordinary level of computational hardness for such problems, and are rare in the current literature: there are only a handful of such lower bounds (for treewidth and vertex cover parameterizations) and all of them are for problems that are #NP-complete, Σ₂^p-complete, Π₂^p-complete, or complete for even higher levels of the polynomial hierarchy. Our results demonstrate, for the first time, that it is not necessary to go higher up in the polynomial hierarchy to achieve double-exponential lower bounds: we derive double-exponential lower bounds in the treewidth (tw) and the vertex cover number (vc), for natural, important, and well-studied NP-complete graph problems. Specifically, we design a technique to obtain such lower bounds and show its versatility by applying it to three different problems: Metric Dimension, Strong Metric Dimension, and Geodetic Set. We prove that these problems do not admit 2^{2^o(tw)}⋅n^𝒪(1)-time algorithms, even on bounded diameter graphs, unless the ETH fails (here, n is the number of vertices in the graph). In fact, for Strong Metric Dimension, the double-exponential lower bound holds even for the vertex cover number. We further complement all our lower bounds with matching (and sometimes non-trivial) upper bounds. For the conditional lower bounds, we design and use a novel, yet simple technique based on Sperner families of sets. We believe that the amenability of our technique will lead to obtaining such lower bounds for many other problems in NP.
History
Editor
Bringmann K ; Grohe M ; Puppis G ; Svensson O
Primary Research Area
Algorithmic Foundations and Cryptography
Name of Conference
International Colloquium on Automata Languages and Programming (ICALP)
Journal
51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)
Volume
297
Page Range
66:1-66:19
Publisher
Schloss Dagstuhl – Leibniz-Zentrum für Informatik
BibTeX
@inproceedings{Foucaud:Galby:Khazaliya:Li:Mc Inerney:Sharma:Tale:2024,
title = "Problems in NP Can Admit Double-Exponential Lower Bounds When Parameterized by Treewidth or Vertex Cover",
author = "Foucaud, Florent" AND "Galby, Esther" AND "Khazaliya, Liana" AND "Li, Shaohua" AND "Mc Inerney, Fionn" AND "Sharma, Roohani" AND "Tale, Prafullkumar",
editor = "Bringmann, Karl" AND "Grohe, Martin" AND "Puppis, Gabriele" AND "Svensson, Ola",
year = 2024,
month = 7,
journal = "51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)",
pages = "66:1--66:19",
publisher = "Schloss Dagstuhl – Leibniz-Zentrum für Informatik",
issn = "1868-8969",
doi = "10.4230/LIPIcs.ICALP.2024.66"
}