Lower Bounds for Dynamic Programming on Planar Graphs of Bounded Cutwidth - van Geffen, Bas; Jansen, Bart; de Kroon, Arnoud; Morel, Rolf (Journal of Graph Algorithms and Applications, 2020)
Many combinatorial problems can be solved in time $\mathcal{O}^*(c^{tw})$ on graphs of treewidth $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-ε)^{ctw})$ time, and $\rm{D{\small OMINATING}~S{\small ET}}$ cannot be solved in $O^*((3-ε)^{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.