  Dynamic programming on path and tree decompositions of graphs is a technique
that is ubiquitous in the field of parameterized and exponential-time
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, '14], we investigate whether this space complexity
explosion is unavoidable. Using the idea of reparameterization of Cai and
Juedes [J. Comput. Syst. Sci., '03], 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 tree-depth. We prove that computations on tree-depth
decompositions correspond to a model of non-deterministic 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
polynomial-time non-deterministic machines with different restrictions on the
access to working space, which mirrors the classic relations between treewidth,
pathwidth, and tree-depth.
