Lower Bounds for Dynamic Programming on Planar Graphs of Bounded Cutwidth

Abstract

Many combinatorial problems can be solved in time $\mathcal{O}^*(c^{\mathrm{tw}})$ on graphs of treewidth $\mathrm{tw}$, for a problem-specific constant $c$. In several cases, matching upper and lower bounds on $c$ are known based on the Strong Exponential Time Hypothesis (SETH). In this paper we investigate the complexity of solving problems on graphs of bounded cutwidth, a graph parameter that takes larger values than treewidth. We strengthen earlier treewidth-based lower bounds to show that, assuming SETH, $\rm{I{\small NDEPENDENT}~S{\small ET}}$ cannot be solved in $O^*((2-\varepsilon)^{\mathrm{ctw}})$ time, and $\rm{D{\small OMINATING}~S{\small ET}}$ cannot be solved in $O^*((3-\varepsilon)^{\mathrm{ctw}})$ time. By designing a new crossover gadget, we extend these lower bounds even to planar graphs of bounded cutwidth or treewidth. Hence planarity does not help when solving $\rm{I{\small NDEPENDENT}~S{\small ET}}$ or $\rm{D{\small OMINATING}~S{\small ET}}$ on graphs of bounded width. This sharply contrasts the fact that in many settings, planarity allows problems to be solved much more efficiently.