The Primal Pathwidth SETH
Michael Lampis · Society for Industrial and Applied Mathematics eBooks · 2025
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 — ∈ )pwnO(1)? (where pw is the pathwidth of the input graph) (ii) can COLORING be solved in time pw(1—∈)pwnO(1)? (iii) can a short reconfiguration between two size-k independent sets be found in time n1-∈)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.