The Primal Pathwidth SETH
CoRR(2024)
摘要
Motivated by the importance of dynamic programming (DP) in parameterized
complexity, we consider several fine-grained questions, such as the following
examples: (i) can Dominating Set be solved in time (3-ϵ)^pwn^O(1)?
(where pw is the pathwidth) (ii) can Coloring be solved in time
pw^(1-ϵ)pwn^O(1)? (iii) can a short reconfiguration between two
size-k independent sets be found in time n^(1-ϵ)k? Such questions
are well-studied: in some cases the answer is No under the SETH, while in
others coarse-grained lower bounds are known under the ETH. Even though
questions such as the above seem "morally equivalent" as they all ask if a
simple DP can be improved, the problems concerned have wildly varying time
complexities, ranging from single-exponential FPT to XNLP-complete.
This paper's main contribution is to show that, despite their varying
complexities, these questions are not just morally equivalent, but in fact they
are the same question in disguise. We achieve this by putting forth a natural
complexity assumption which we call the Primal Pathwidth-Strong Exponential
Time Hypothesis (PP-SETH) and which states that 3-SAT cannot be solved in time
(2-ϵ)^pwn^O(1), for any ϵ>0, where pw is the pathwidth
of the primal graph of the input. We then show that numerous fine-grained
questions in parameterized complexity, including the ones above, are equivalent
to the PP-SETH, and hence to each other. This allows us to obtain sharp
fine-grained lower bounds for problems for which previous lower bounds left a
constant in the exponent undetermined, but also to increase our confidence in
bounds which were previously known under the SETH, because we show that
breaking any one such bound requires breaking all (old and new) bounds; and
because we show that the PP-SETH is more plausible than the SETH.
更多查看译文
AI 理解论文
溯源树
样例
生成溯源树,研究论文发展脉络
Chat Paper
正在生成论文摘要