Lower Bounds for Dynamic Programming on Planar Graphs of Bounded Cutwidth

Bas A. M. van Geffen, Bart M. P. Jansen, Arnoud A. W. M. de Kroon +1

Many combinatorial problems can be solved in time $O^{\ast }(c^{tw})$ on graphs of treewidth $tw$, for a problem-specific constant $c$. In several cases, matching upper and lower bounds…