  Dynamic programming on various graph decompositions is one of the most
fundamental techniques used in parameterized complexity. Unfortunately, even if
we consider concepts as simple as path or tree decompositions, such dynamic
programming uses space that is exponential in the decomposition's width, and
there are good reasons to believe that this is necessary. However, it has been
shown that in graphs of low treedepth it is possible to design algorithms which
achieve polynomial space complexity without requiring worse time complexity
than their counterparts working on tree decompositions of bounded width. Here,
treedepth is a graph parameter that, intuitively speaking, takes into account
both the depth and the width of a tree decomposition of the graph, rather than
the width alone.
  Motivated by the above, we consider graphs that admit clique expressions with
bounded depth and label count, or equivalently, graphs of low shrubdepth (sd).
Here, sd is a bounded-depth analogue of cliquewidth, in the same way as td is a
bounded-depth analogue of treewidth. We show that also in this setting,
bounding the depth of the decomposition is a deciding factor for improving the
space complexity. Precisely, we prove that on $n$-vertex graphs equipped with a
tree-model (a decomposition notion underlying sd) of depth $d$ and using $k$
labels, we can solve
  - Independent Set in time $2^{O(dk)}\cdot n^{O(1)}$ using $O(dk^2\log n)$
space;
  - Max Cut in time $n^{O(dk)}$ using $O(dk\log n)$ space; and
  - Dominating Set in time $2^{O(dk)}\cdot n^{O(1)}$ using $n^{O(1)}$ space via
a randomized algorithm.
  We also establish a lower bound, conditional on a certain assumption about
the complexity of Longest Common Subsequence, which shows that at least in the
case of IS the exponent of the parametric factor in the time complexity has to
grow with $d$ if one wishes to keep the space complexity polynomial.
