Lower Bounds on Dynamic Programming for Connectivity Problems

This paper provides lower bounds on the complexity of pure dynamic programming algorithms (modeled by tropical circuits) for connectivity problems like the Traveling Salesperson Problem on graphs with bounded pathwidth. The results suggest that algebraic techniques are crucial for achieving optimal performance, as pure dynamic programming approaches face significant limitations. The paper's contribution lies in establishing these limitations and providing evidence for the necessity of algebraic methods in designing efficient algorithms for these problems.