Lower bounds for dynamic programming on planar graphs of bounded cutwidth

B.A.M. van Geffen; Bart M.P. Jansen; A.A.W.M. de Kroon; Rolf Morel

doi:10.4230/LIPIcs.IPEC.2018.3

Lower bounds for dynamic programming on planar graphs of bounded cutwidth

B.A.M. van Geffen, Bart M.P. Jansen, A.A.W.M. de Kroon, Rolf Morel

Algorithms, Geometry and Applications

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

63 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 language	English
Title of host publication	13th International Symposium on Parameterized and Exact Computation (IPEC 2018)
Editors	Christophe Paul, Michal Pilipczuk
Publisher	Schloss Dagstuhl - Leibniz-Zentrum für Informatik
Number of pages	14
ISBN (Electronic)	978-3-95977-084-2
DOIs	https://doi.org/10.4230/LIPIcs.IPEC.2018.3
Publication status	Published - 1 Jan 2019
Event	13th International Symposium on Parameterized and Exact Computation, IPEC 2018 - Helsinki, Finland Duration: 20 Aug 2018 → 24 Aug 2018 Conference number: 13 http://algo2018.hiit.fi/ipec/

Publication series

Name	Leibniz International Proceedings in Informatics, LIPIcs
Volume	115
ISSN (Print)	1868-8969

Conference

Conference	13th International Symposium on Parameterized and Exact Computation, IPEC 2018
Abbreviated title	IPEC 2018
Country/Territory	Finland
City	Helsinki
Period	20/08/18 → 24/08/18
Internet address	http://algo2018.hiit.fi/ipec/

Keywords

Cutwidth
Dominating set
Lower bounds
Planarization
Strong exponential time hypothesis

Access to Document

10.4230/LIPIcs.IPEC.2018.3

publishers versionFinal published version, 686 KB

Cite this

van Geffen, B. A. M., Jansen, B. M. P., de Kroon, A. A. W. M., & Morel, R. (2019). Lower bounds for dynamic programming on planar graphs of bounded cutwidth. In C. Paul, & M. Pilipczuk (Eds.), 13th International Symposium on Parameterized and Exact Computation (IPEC 2018) [3] (Leibniz International Proceedings in Informatics, LIPIcs; Vol. 115). Schloss Dagstuhl - Leibniz-Zentrum für Informatik. https://doi.org/10.4230/LIPIcs.IPEC.2018.3

van Geffen, B.A.M. ; Jansen, Bart M.P. ; de Kroon, A.A.W.M. et al. / Lower bounds for dynamic programming on planar graphs of bounded cutwidth. 13th International Symposium on Parameterized and Exact Computation (IPEC 2018). editor / Christophe Paul ; Michal Pilipczuk. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2019. (Leibniz International Proceedings in Informatics, LIPIcs).

@inproceedings{626817911b1f4908a11bf427f138d867,

title = "Lower bounds for dynamic programming on planar graphs of bounded cutwidth",

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.",

keywords = "Cutwidth, Dominating set, Lower bounds, Planarization, Strong exponential time hypothesis",

author = "{van Geffen}, B.A.M. and Jansen, {Bart M.P.} and {de Kroon}, A.A.W.M. and Rolf Morel",

year = "2019",

month = jan,

day = "1",

doi = "10.4230/LIPIcs.IPEC.2018.3",

language = "English",

series = "Leibniz International Proceedings in Informatics, LIPIcs",

publisher = "Schloss Dagstuhl - Leibniz-Zentrum f{\"u}r Informatik",

editor = "Christophe Paul and Michal Pilipczuk",

booktitle = "13th International Symposium on Parameterized and Exact Computation (IPEC 2018)",

note = "13th International Symposium on Parameterized and Exact Computation, IPEC 2018, IPEC 2018 ; Conference date: 20-08-2018 Through 24-08-2018",

url = "http://algo2018.hiit.fi/ipec/",

}

van Geffen, BAM, Jansen, BMP, de Kroon, AAWM & Morel, R 2019, Lower bounds for dynamic programming on planar graphs of bounded cutwidth. in C Paul & M Pilipczuk (eds), 13th International Symposium on Parameterized and Exact Computation (IPEC 2018)., 3, Leibniz International Proceedings in Informatics, LIPIcs, vol. 115, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 13th International Symposium on Parameterized and Exact Computation, IPEC 2018, Helsinki, Finland, 20/08/18. https://doi.org/10.4230/LIPIcs.IPEC.2018.3

Lower bounds for dynamic programming on planar graphs of bounded cutwidth. / van Geffen, B.A.M.; Jansen, Bart M.P.; de Kroon, A.A.W.M. et al.
13th International Symposium on Parameterized and Exact Computation (IPEC 2018). ed. / Christophe Paul; Michal Pilipczuk. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2019. 3 (Leibniz International Proceedings in Informatics, LIPIcs; Vol. 115).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

TY - GEN

T1 - Lower bounds for dynamic programming on planar graphs of bounded cutwidth

AU - van Geffen, B.A.M.

AU - Jansen, Bart M.P.

AU - de Kroon, A.A.W.M.

AU - Morel, Rolf

N1 - Conference code: 13

PY - 2019/1/1

Y1 - 2019/1/1

N2 - 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.

AB - 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.

KW - Cutwidth

KW - Dominating set

KW - Lower bounds

KW - Planarization

KW - Strong exponential time hypothesis

UR - http://www.scopus.com/inward/record.url?scp=85092547880&partnerID=8YFLogxK

U2 - 10.4230/LIPIcs.IPEC.2018.3

DO - 10.4230/LIPIcs.IPEC.2018.3

M3 - Conference contribution

T3 - Leibniz International Proceedings in Informatics, LIPIcs

BT - 13th International Symposium on Parameterized and Exact Computation (IPEC 2018)

A2 - Paul, Christophe

A2 - Pilipczuk, Michal

PB - Schloss Dagstuhl - Leibniz-Zentrum für Informatik

T2 - 13th International Symposium on Parameterized and Exact Computation, IPEC 2018

Y2 - 20 August 2018 through 24 August 2018

ER -

van Geffen BAM, Jansen BMP, de Kroon AAWM, Morel R. Lower bounds for dynamic programming on planar graphs of bounded cutwidth. In Paul C, Pilipczuk M, editors, 13th International Symposium on Parameterized and Exact Computation (IPEC 2018). Schloss Dagstuhl - Leibniz-Zentrum für Informatik. 2019. 3. (Leibniz International Proceedings in Informatics, LIPIcs). doi: 10.4230/LIPIcs.IPEC.2018.3

Lower bounds for dynamic programming on planar graphs of bounded cutwidth

Abstract

Publication series

Conference

Keywords

Access to Document

Other files and links

Fingerprint

Cite this