2026-08-06T13:26:36Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:10204 2024-03-06T10:44:15Z ddc:004 open_access

Lower Bounds for Dynamic Programming on Planar Graphs of Bounded Cutwidth van Geffen, Bas A. M. Jansen, Bart M. P. de Kroon, Arnoud A. W. M. Morel, Rolf planarization dominating set cutwidth lower bounds strong exponential time hypothesis Many combinatorial problems can be solved in time 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, Independent Set cannot be solved in O^*((2-epsilon)^{ctw}) time, and Dominating Set cannot be solved in O^*((3-epsilon)^{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 Independent Set or Dominating Set on graphs of bounded width. This sharply contrasts the fact that in many settings, planarity allows problems to be solved much more efficiently. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Bas A. M. van Geffen and Bart M. P. Jansen and Arnoud A. W. M. de Kroon and Rolf Morel 2019 Is Part Of LIPIcs, Volume 115, 13th International Symposium on Parameterized and Exact Computation (IPEC 2018) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.IPEC.2018.3 urn:nbn:de:0030-drops-102049 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2018.3 eng https://creativecommons.org/licenses/by/3.0/legalcode