1 Search Results for "Morel, Rolf"


Document
Lower Bounds for Dynamic Programming on Planar Graphs of Bounded Cutwidth

Authors: Bas A. M. van Geffen, Bart M. P. Jansen, Arnoud A. W. M. de Kroon, and Rolf Morel

Published in: LIPIcs, Volume 115, 13th International Symposium on Parameterized and Exact Computation (IPEC 2018)


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.

Cite as

Bas A. M. van Geffen, Bart M. P. Jansen, Arnoud A. W. M. de Kroon, and Rolf Morel. Lower Bounds for Dynamic Programming on Planar Graphs of Bounded Cutwidth. In 13th International Symposium on Parameterized and Exact Computation (IPEC 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 115, pp. 3:1-3:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)


Copy BibTex To Clipboard

@InProceedings{vangeffen_et_al:LIPIcs.IPEC.2018.3,
  author =	{van Geffen, Bas A. M. and Jansen, Bart M. P. and de Kroon, Arnoud A. W. M. and Morel, Rolf},
  title =	{{Lower Bounds for Dynamic Programming on Planar Graphs of Bounded Cutwidth}},
  booktitle =	{13th International Symposium on Parameterized and Exact Computation (IPEC 2018)},
  pages =	{3:1--3:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-084-2},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{115},
  editor =	{Paul, Christophe and Pilipczuk, Michal},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2018.3},
  URN =		{urn:nbn:de:0030-drops-102049},
  doi =		{10.4230/LIPIcs.IPEC.2018.3},
  annote =	{Keywords: planarization, dominating set, cutwidth, lower bounds, strong exponential time hypothesis}
}
  • Refine by Author
  • 1 Jansen, Bart M. P.
  • 1 Morel, Rolf
  • 1 de Kroon, Arnoud A. W. M.
  • 1 van Geffen, Bas A. M.

  • Refine by Classification
  • 1 Theory of computation → Graph algorithms analysis
  • 1 Theory of computation → Parameterized complexity and exact algorithms

  • Refine by Keyword
  • 1 cutwidth
  • 1 dominating set
  • 1 lower bounds
  • 1 planarization
  • 1 strong exponential time hypothesis

  • Refine by Type
  • 1 document

  • Refine by Publication Year
  • 1 2019

Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail