2026-09-08T02:22:06Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:26519 2026-09-05T19:46:15Z ddc:004 open_access

Lower Bounds on Pure Dynamic Programming for Connectivity Problems on Graphs of Bounded Path-Width Kluk, Kacper Nederlof, Jesper Parameterized Complexity treewidth tropical circuits connectivity problems We give unconditional parameterized complexity lower bounds on pure dynamic programming algorithms - as modeled by tropical circuits - for connectivity problems such as the Traveling Salesperson Problem. Our lower bounds are higher than the currently fastest algorithms that rely on algebra and give evidence that these algebraic aspects are unavoidable for competitive worst case running times. Specifically, we study input graphs with a small width parameter such as treewidth and pathwidth and show that for any k there exists a graph G of pathwidth at most k and k^𝒪(1) vertices such that any tropical circuit calculating the optimal value of a Traveling Salesperson round tour uses at least 2^Ω(k log log k) gates. We establish this result by linking tropical circuit complexity to the nondeterministic communication complexity of specific compatibility matrices. These matrices encode whether two partial solutions combine into a full solution, and Raz and Spieker [Combinatorica 1995] previously proved a lower bound for this complexity measure. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Kacper Kluk and Jesper Nederlof 2026 Is Part Of LIPIcs, Volume 374, 53rd International Colloquium on Automata, Languages, and Programming (ICALP 2026) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ICALP.2026.130 urn:nbn:de:0030-drops-265196 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2026.130 eng https://creativecommons.org/licenses/by/4.0/legalcode