The Primal Pathwidth SETH

Motivated by the importance of dynamic programming (DP) in parameterized complexity, we consider several fundamental fine-grained questions, such as the following representative examples: (i) can Dominating Set be solved in time (3 -ε) pw n O(1) ? (where pw is the pathwidth of the input graph) (ii) can Coloring be solved in time pw (1-ε)pw n 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 (pw-SETH) and which states that 3-SAT cannot be solved in time (2 -ε) pw n O(1) , for any ε > 0, where pw is the pathwidth of the primal graph of the input CNF formula. We then show that numerous fine-grained questions in parameterized complexity, including the ones above, are equivalent to the pw-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 pw-SETH is more plausible than the SETH. More broadly, our results indicate that pw-SETH-equivalence is a meta-complexity property that cuts across traditional complexity classes, because it exactly captures the barrier impeding progress not only for problems solvable in time c k n O(1) (such as 3-SAT itself for parameter pw), but also for problems which are considerably harder.

In more detail, we show that all of the following are equivalent to falsifying the pw-SETH:

1. Single-exponential FPT problems: solving k-Coloring in time (k -ε) pw n O(1) or (2 k -2) lcw n O(1) , for any k ≥ 3, where lcw is the linear clique-width; solving Distance-d-Independent Set in time 1) . For the latter problem we give an algorithm tightly matching this complexity. 3. XNLP-complete problems: solving List Coloring in time n (1-ε)pw ; finding a short word accepted by k n-state DFAs in time n (1-ε)k ; finding a short reconfiguration sequence between two size-k independent sets of an n-vertex graph in time n (1-ε)k .

We argue that the pw-SETH is a plausible assumption by showing that it is implied not only by the SETH, but also by a maximization version of the k-Orthogonal Vectors Assumption (itself a consequence of the SETH) and by the Set Cover Conjecture, whose relation to the SETH is a major open problem. Hence, lower bounds which were previously known under the SETH, such as those of point 1 above, are now shown to also be implied by these conjectures.