License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.STACS.2020.29
URN: urn:nbn:de:0030-drops-118907
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2020/11890/
Go to the corresponding LIPIcs Volume Portal

Hegerfeld, Falko ; Kratsch, Stefan

Solving Connectivity Problems Parameterized by Treedepth in Single-Exponential Time and Polynomial Space

pdf-format:
LIPIcs-STACS-2020-29.pdf (0.6 MB)

Abstract

A breakthrough result of Cygan et al. (FOCS 2011) showed that connectivity problems parameterized by treewidth can be solved much faster than the previously best known time ?^*(2^{?(twlog tw)}). Using their inspired Cut&Count technique, they obtained ?^*(α^tw) time algorithms for many such problems. Moreover, they proved these running times to be optimal assuming the Strong Exponential-Time Hypothesis. Unfortunately, like other dynamic programming algorithms on tree decompositions, these algorithms also require exponential space, and this is widely believed to be unavoidable. In contrast, for the slightly larger parameter called treedepth, there are already several examples of matching the time bounds obtained for treewidth, but using only polynomial space. Nevertheless, this has remained open for connectivity problems.
In the present work, we close this knowledge gap by applying the Cut&Count technique to graphs of small treedepth. While the general idea is unchanged, we have to design novel procedures for counting consistently cut solution candidates using only polynomial space. Concretely, we obtain time ?^*(3^d) and polynomial space for Connected Vertex Cover, Feedback Vertex Set, and Steiner Tree on graphs of treedepth d. Similarly, we obtain time ?^*(4^d) and polynomial space for Connected Dominating Set and Connected Odd Cycle Transversal.

BibTeX - Entry

@InProceedings{hegerfeld_et_al:LIPIcs:2020:11890,
  author =	{Falko Hegerfeld and Stefan Kratsch},
  title =	{{Solving Connectivity Problems Parameterized by Treedepth in Single-Exponential Time and Polynomial Space}},
  booktitle =	{37th International Symposium on Theoretical Aspects of Computer Science (STACS 2020)},
  pages =	{29:1--29:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-140-5},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{154},
  editor =	{Christophe Paul and Markus Bl{\"a}ser},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2020/11890},
  URN =		{urn:nbn:de:0030-drops-118907},
  doi =		{10.4230/LIPIcs.STACS.2020.29},
  annote =	{Keywords: Parameterized Complexity, Connectivity, Treedepth, Cut&Count, Polynomial Space}
}

Keywords: Parameterized Complexity, Connectivity, Treedepth, Cut&Count, Polynomial Space
Collection: 37th International Symposium on Theoretical Aspects of Computer Science (STACS 2020)
Issue Date: 2020
Date of publication: 04.03.2020

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI