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

Kacper Kluk, Jesper Nederlof

We give unconditional parameterized complexity lower bounds on pure dynamic programming algorithms - as modeled by tropical circuits - for connectivity problems such as the Traveli…