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.

We show that for any fixed integer k ⩾ 0, there exists an algorithm that computes the diameter and the eccentricies of all vertices of an input unweighted, undirected n-vertex graph of Euler genus at most k in time 𝒪_k(n^{2-1/25}). Furthermore, for the more general class of graphs that can be constructed by clique-sums from graphs that are of Euler genus at most k after deletion of at most k vertices, we show an algorithm for the same task that achieves the running time bound 𝒪_k(n^{2-1/356} log^{6k} n). Up to today, the only known subquadratic algorithms for computing the diameter in those graph classes are that of [Ducoffe, Habib, Viennot; SICOMP 2022], [Le, Wulff-Nilsen; SODA 2024], and [Duraj, Konieczny, Potępa; ESA 2024]. These algorithms work in the more general setting of K_h-minor-free graphs, but the running time bound is 𝒪_h(n^{2-c_h}) for some constant c_h > 0 depending on h. That is, our savings in the exponent of the polynomial function of n, as compared to the naive quadratic algorithm, are independent of the parameter k. The main technical ingredient of our work is an improved bound on the number of distance profiles, as defined in [Le, Wulff-Nilsen; SODA 2024], in graphs of bounded Euler genus.

Many natural computational problems, including e.g. Max Weight Independent Set, Feedback Vertex Set, or Vertex Planarization, can be unified under an umbrella of finding the largest sparse induced subgraph that satisfies some property definable in CMSO₂ logic. It is believed that each problem expressible with this formalism can be solved in polynomial time in graphs that exclude a fixed path as an induced subgraph. This belief is supported by the existence of a quasipolynomial-time algorithm by Gartland, Lokshtanov, Pilipczuk, Pilipczuk, and Rzążewski [STOC 2021], and a recent polynomial-time algorithm for P₆-free graphs by Chudnovsky, McCarty, Pilipczuk, Pilipczuk, and Rzążewski [SODA 2024]. In this work we extend polynomial-time tractability of all such problems to P₇-free graphs of bounded clique number.