TY - GEN
T1 - Tight Double Exponential Lower Bounds
AU - Bliznets, Ivan
AU - Hecher, Markus
N1 - Publisher Copyright:
© The Author(s), under exclusive license to Springer Nature Singapore Pte Ltd. 2024.
PY - 2024/5/3
Y1 - 2024/5/3
N2 - The majority of established algorithms have polynomial, exponential, or factorial runtime complexities. Examples of problems that admit tight double or even triple exponential bounds on computational complexity are relatively rare. The Choosability problem is one such example. For this problem, Marx and Mitsou [ICALP 2016] presented a quite sophisticated proof that shows there is no O(22o(tw))nO(1) time algorithm parameterized by treewidth tw, assuming ETH. In our paper, we show how we almost immediately come to the same conclusion knowing the reduction from ∀∃-TQBF to the Choosability problem. Besides, in some sense, we provide a factory that produces problems with tight double exponential lower bounds not only in terms of treewidth but also pathwidth, cutwidth, and bandwidth. It was suspected that the Π2P-complete or Σ2P-complete problems require a double exponential time algorithm in terms of treewidth. However, in our paper, we provide a counterexample to this statement.
AB - The majority of established algorithms have polynomial, exponential, or factorial runtime complexities. Examples of problems that admit tight double or even triple exponential bounds on computational complexity are relatively rare. The Choosability problem is one such example. For this problem, Marx and Mitsou [ICALP 2016] presented a quite sophisticated proof that shows there is no O(22o(tw))nO(1) time algorithm parameterized by treewidth tw, assuming ETH. In our paper, we show how we almost immediately come to the same conclusion knowing the reduction from ∀∃-TQBF to the Choosability problem. Besides, in some sense, we provide a factory that produces problems with tight double exponential lower bounds not only in terms of treewidth but also pathwidth, cutwidth, and bandwidth. It was suspected that the Π2P-complete or Σ2P-complete problems require a double exponential time algorithm in terms of treewidth. However, in our paper, we provide a counterexample to this statement.
KW - Choosability
KW - double exponential
KW - lower bounds
UR - http://www.scopus.com/inward/record.url?scp=85193248112&partnerID=8YFLogxK
U2 - 10.1007/978-981-97-2340-9_11
DO - 10.1007/978-981-97-2340-9_11
M3 - Conference contribution
AN - SCOPUS:85193248112
SN - 978-981-97-2339-3
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 124
EP - 136
BT - Theory and Applications of Models of Computation - 18th Annual Conference, TAMC 2024, Proceedings
A2 - Chen, Xujin
A2 - Li, Bo
PB - Springer
T2 - 18th Annual Conference on Theory and Applications of Models of Computation, TAMC 2024
Y2 - 13 May 2024 through 15 May 2024
ER -