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, Rolf Morel

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

13 Downloads (Pure)

Abstract

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.
Original languageEnglish
Title of host publication13th International Symposium on Parameterized and Exact Computation (IPEC 2018)
EditorsChristophe Paul, Michal Pilipczuk
PublisherSchloss Dagstuhl - Leibniz-Zentrum für Informatik
Number of pages14
ISBN (Electronic)978-3-95977-084-2
DOIs
Publication statusPublished - 1 Jan 2019
Event13th International Symposium on Parameterized and Exact Computation - Helsinki, Finland
Duration: 20 Aug 201824 Aug 2018
http://algo2018.hiit.fi/ipec/

Publication series

NameLeibniz International Proceedings in Informatics, LIPIcs
Volume115
ISSN (Print)1868-8969

Conference

Conference13th International Symposium on Parameterized and Exact Computation
Abbreviated titleIPEC 2018
CountryFinland
CityHelsinki
Period20/08/1824/08/18
Internet address

Keywords

  • Cutwidth
  • Dominating set
  • Lower bounds
  • Planarization
  • Strong exponential time hypothesis

Fingerprint Dive into the research topics of 'Lower bounds for dynamic programming on planar graphs of bounded cutwidth'. Together they form a unique fingerprint.

Cite this