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, and Rolf Morel
Vol. 24, no. 3, pp. 461-482, 2020. Regular paper.
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.
Submitted: December 2018.
Reviewed: August 2020.
Revised: September 2020.
Accepted: September 2020.
Final: October 2020.
Published: October 2020.
Communicated by Gerhard J. Woeginger
article (PDF)