Abstract
Dynamic programming on path and tree decompositions of graphs is a technique that is ubiquitous in the field of parameterized and exponentialtime algorithms. However, one of its drawbacks is that the space usage is exponential in the decomposition's width. Following the work of Allender et al. [Theory of Computing, 2014], we investigate whether this space complexity explosion is unavoidable. Using the idea of reparameterization of Cai and Juedes [J. Comput. Syst. Sci., 2003], we prove that the question is closely related to a conjecture that the Longest Common Subsequence problem parameterized by the number of input strings does not admit an algorithm that simultaneously uses XP time and FPT space. Moreover, we complete the complexity landscape sketched for pathwidth and treewidth by Allender et al. by considering the parameter treedepth. We prove that computations on treedepth decompositions correspond to a model of nondeterministic machines that work in polynomial time and logarithmic space, with access to an auxiliary stack of maximum height equal to the decomposition's depth. Together with the results of Allender et al., this describes a hierarchy of complexity classes for polynomialtime non deterministic machines with different restrictions on the access to working space, which mirrors the classic relations between treewidth, pathwidth, and treedepth.
BibTeX  Entry
@InProceedings{pilipczuk_et_al:LIPIcs:2016:5758,
author = {Michal Pilipczuk and Marcin Wrochna},
title = {{On Space Efficiency of Algorithms Working on Structural Decompositions of Graphs}},
booktitle = {33rd Symposium on Theoretical Aspects of Computer Science (STACS 2016)},
pages = {57:157:15},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959770019},
ISSN = {18688969},
year = {2016},
volume = {47},
editor = {Nicolas Ollinger and Heribert Vollmer},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2016/5758},
URN = {urn:nbn:de:0030drops57588},
doi = {10.4230/LIPIcs.STACS.2016.57},
annote = {Keywords: tree decomposition, LCS, treedepth, NAuxSA, Savitch’s theorem}
}
Keywords: 

tree decomposition, LCS, treedepth, NAuxSA, Savitch’s theorem 
Seminar: 

33rd Symposium on Theoretical Aspects of Computer Science (STACS 2016) 
Issue Date: 

2016 
Date of publication: 

16.02.2016 