Skip to Main content Skip to Navigation
Master Thesis

The role of planarity in connectivity problems parameterized by treewidth

Abstract : For some years, it was believed that for "connectivity" problems such as Hamiltonian Cycle, algorithms running in time 2O(tw) nO(1) -called singleexponential- existed only on planar and other sparse graph classes, where tw stands for the treewidth of the n-vertex input graph. This was recently disproved by Cygan et al. [FOCS 2011] and Bodlaender et al. [ICALP 2013], who provided single-exponential algorithms on general graphs for essentially all connectivity problems that were known to be solvable in single-exponential time on sparse graphs. During my internship, we further investigate the role of planarity in connectivity problems parameterized by treewidth, and convey that several problems can indeed be distinguished according to their behavior on planar graphs. In particular, we show that there exist problems that cannot be solved in time 2o(twlog tw) nO(1) on general graphs but that can be solved in time 2O(tw) nO(1) when restricted to planar graphs, and problems that can be solved in time 2O(twlog tw) nO(1) on general graphs but that cannot be solved in time 2o(twlog tw) nO(1) even when restricted to planar graphs, the negative results holding unless the ETH fails. We feel that our results constitute a first step in a subject that can be much exploited.
Document type :
Master Thesis
Complete list of metadata

Cited literature [22 references]  Display  Hide  Download

https://dumas.ccsd.cnrs.fr/dumas-00854884
Contributor : Co-Responsables Du Mri V. Gouranton Et S. Blazy <>
Submitted on : Wednesday, August 28, 2013 - 12:03:29 PM
Last modification on : Monday, February 15, 2021 - 10:37:16 AM
Long-term archiving on: : Thursday, April 6, 2017 - 9:41:18 AM

Identifiers

  • HAL Id : dumas-00854884, version 1

Citation

Julien Baste. The role of planarity in connectivity problems parameterized by treewidth. Data Structures and Algorithms [cs.DS]. 2013. ⟨dumas-00854884⟩

Share

Metrics

Record views

352

Files downloads

345