  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 $\mathcal{O}^*(2^{\mathcal{O}(tw \log(tw))})$. Using
their inspired Cut\&Count technique, they obtained $\mathcal{O}^*(\alpha^{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 algorithms
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
$\mathcal{O}^*(3^d)$ and polynomial space for Connected Vertex Cover, Feedback
Vertex Set, and Steiner Tree on graphs of treedepth $d$. Similarly, we obtain
time $\mathcal{O}^*(4^d)$ and polynomial space for Connected Dominating Set and
Connected Odd Cycle Transversal.
