Lower bounds on pure dynamic programming for connectivity problems on graphs of bounded path-width

Kacper Kluk, Jesper Nederlof · 2025

Read Lower bounds on pure dynamic programming for connectivity problems on graphs of bounded path-width by Kacper Kluk, Jesper Nederlof (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2512-23121.txt.

Introduction

Kacper Kluk and Jesper Nederlof prove hard limits on what plain dynamic programming can achieve for connectivity problems like the Traveling Salesperson Problem. Their model of pure dynamic programming is the tropical circuit, and they study inputs whose graphs have small pathwidth, the regime where dynamic programming is usually strongest. The bounds are unconditional, not resting on unproved complexity assumptions.

For every width k, they exhibit a graph of pathwidth at most k on a modest number of vertices. For that graph, any tropical circuit computing the optimal tour value needs a gate count growing faster than exponentially in k. The proof connects tropical circuit size to nondeterministic communication complexity of compatibility matrices, importing a lower bound of Raz and Spieker. The message is that the fastest known algorithms' reliance on algebra is not a stylistic choice: pure dynamic programming provably cannot match them.

Catalog record

CREATORKacper Kluk, Jesper Nederlof
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE69 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2512-23121

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Lower bounds on pure dynamic programming for connectivity problems on graphs of bounded path-width Thanks: K.K. is supported by Polish National Science Centre SONATA BIS-12 grant number 2022/46/E/ST6/00143. J.N is supported by the project COALESCE that has received funding from the European Research Council (ERC), grant agreement No 853234. Kacper Kluk, Jesper Nederlof Abstract 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 k there exists a graph G G of pathwidth at most k k and k O ⁡ ( 1 ) k^{O(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 ) 2^{\Omega(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. 1 Introduction A common paradigm in theoretical computer science is to pin down which algorithmic techniques can or cannot achieve certain central goals by formalizing such a technique within a precise algorithmic model and then proving sharp limitations for that model. Classic examples include unconditional lower bounds for Linear Programming-based algorithms (i.e. extension complexity [ 11 , 27 ] ), conditional lower bounds for preprocessing algorithms in parameterized complexity (conditioned on the non-collapse of the polynomial hierarchy [ 5 , 14 ] ), and unconditional lower bounds for resolution-based algorithms for refuting the Strong Exponential Time Hypothesis [ 1 ] . This paradigm reveals which algorithmic nuances are fundamentally unavoidable and shows us where genuine breakthroughs must come from. One notable example of such algorithmic nuance is that of algebraic cancellation: for several combinatorial computational problems, the fastest known algorithms crucially exploit certain algebraic cancellation in rather counter-intuitive ways, and it is a well-studied open question whether these algorithms can be matched with (more natural, and in some sense robust) ‘combinatorial’ algorithms. This question arises for instance in the settings of Boolean matrix multiplication [ 28 ] , various variants of the problem of finding a perfect matching solvable by reduction to determinant computation [ 18 , 24 ] , and fast exponential time algorithms for Hamiltonicity [ 3 ] . This very question of whether the use of algebraic cancellation is needed does not only occur in algorithm design, but also in various other disciplines. For example, in extremal combinatorics, it is an open question in various settings whether combinatorial proofs exist that match algebraic proofs (for example, a combinatorial proof of the skew two families theorem remains illusive [ 6 ] ), and the log rank conjecture in communication complexity asks whether algebraic low rank decompositions of matrices in general imply low rank combinatorial decompositions (or more specifically, whether the rank and partioning number of a Boolean matrix are quasi-polynomially related), see e.g. [ 23 ] . One such setting in which we would like to replace algebraic arguments with combinatorial arguments within the area of parameterized complexity is that of connectivity problems parameterized by treewidth: In 2011 it was shown that that many connectivity problems parameterized by treewidth can be solved faster than what was deemed possible at the time [ 10 ] . In particular, problems like Hamiltonian Cycle and Steiner tree were solved with a randomized algorithm in 2^{O(k)}N^{O(1)} time, when given a tree decomposition of width k of an N -vertex input graph. Before this work, fastest known algorithm for problems parameterized by treewidth were based on straightforward combinatorial dynamic programming techniques that naturally lead to running times like k^{O(k)}N^{O(1)} and seemed hard to improve. Later work that followed up on [ 10 ] and provided deterministic algorithms for weighted extensions such as the Traveling Salesperson Problem (TSP) on bounded treewidth graphs [ 4 ] and an alternative version connected the approach with a matroid-based extension of the aforementioned two-family theorem [ 13 ] . All these works [ 10 , 4 , 13 ] rely on algebraic cancellation by exploiting that the rank of certain compatibility matrices is small, a particularly counterintuitive approach in comparison to the previous simple and clean combinatorial k^{O(k)}N^{O(1)} time algorithms. It is a notable open question to remove the mentioned overhead in the runtime for the deterministic algorithm and weighted extensions. For example, a positive resolution of this open question would bring us closer to solving the TSP in time 1.9999^{N} [ 25 ] , where N is the number of cities. But, to do so it seems crucial to get a better combinatorial understanding of the involved compatibility matrices, simultaneously bypassing the undesired algebraic cancellation arguments. In this work we give a strong indication that more than just elementary combinatorial techniques are needed, via the algorithmic model of tropical circuits . Tropical Circuits. A tropical circuit is an arithmetic circuit in which the inputs are labeled with variables that take an integer as value and the two arithmetic gates correspond to the max and sum, or alternatively, min and sum, operations. See Section 2 for a precise definition. The motivation for studying the expressiveness of tropical circuits is that it models a broad class dynamic programming algorithm. In particular, if there exists for a maximization problem (for which its instances are defined by a set of input weights) a dynamic programming algorithm that is ‘pure’ in the sense that the associated recurrence only features the operations max and sum, than there is tropical circuit that outputs the optimal objective value with circuit size being proportional to the running time of the dynamic programming algorithm. For example the classic Bellman-Held-Karp [ 2 , 15 ] O(N^{2}2^{N}) time algorithm for TSP is naturally converted into a tropical circuit with O(N^{2}2^{N}) gates and the O(N^{3}) time Floyd-Warshall [ 12 , 29 ] algorithm that computes the shortest path lengths between each pair of vertices is naturally converted into a tropical circuit with O(N^{3}) gates. Both tropical circuits cannot be substantially improved [ 16 , 19 ] (see also [ 17 , Corollary 2.2] ). In the realm of parameterized complexity, it is easy to see that canonical applications of dynamic programming can be modeled in an efficient way as tropical circuits. Examples are the dynamic programming algorithms for Steiner Tree and Set Cover (see e.g. [ 8 , Section 6.1] ) with few number of terminals and elements and, especially relevant for this paper, the O(2^{k}N) time algorithm for the maximum independent set problem on graphs with a given tree decomposition of width k and N vertices. For much more detail on tropical circuits, we refer to the excellent textbook by Jukna [ 17 ] . Problems parameterized by treewidth. A very popular research line that started in

Read the complete text