Lower bounds on pure dynamic programming for connectivity problems on graphs of bounded path-width
Fuente:
arXiv
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866912793522864128 |
|---|---|
| author | Kluk, Kacper Nederlof, Jesper |
| author_facet | Kluk, Kacper Nederlof, Jesper |
| contents | 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^{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)}$ 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2512_23121 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Lower bounds on pure dynamic programming for connectivity problems on graphs of bounded path-width Kluk, Kacper Nederlof, Jesper Computational Complexity Data Structures and Algorithms 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^{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)}$ 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. |
| title | Lower bounds on pure dynamic programming for connectivity problems on graphs of bounded path-width |
| topic | Computational Complexity Data Structures and Algorithms |
| url | https://arxiv.org/abs/2512.23121 |