Solving connectivity problems parameterized by treedepth in singleexponential time and polynomial space. 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 mathcalO*(2mathcalO(tw log(tw))). Using their inspired Cutu0026Count technique, they obtained mathcalO*(alphatw) time algorithms for many such problems. Moreover, they proved these running times to be optimal assuming the Strong ExponentialTime 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.  the :115,present work, we close this knowledge gap by applying the Cutu0026Count 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 mathcalO*(3d) and polynomial space for Connected Vertex Cover, Feedback Vertex Set, and Steiner Tree on graphs of treedepth d. Similarly, we obtain time mathcalO*(4d) and polynomial space for Connected Dominating Set and Connected Odd Cycle Transversal.

Hitting minors on bounded treewidth graphs. II. Singleexponential algorithms Abstract   For a finite collection of graphs    F   , the    F    MDeletion  (resp.    F    TMDeletion ) problem consists in, given a graph G and an integer k, decide whether there exists    S  xe2x8ax86  V  (  G  )    with      S    xe2x89xa4  k    such that    G  xe2x88x96  S    does not contain any of the graphs in    F    as a minor (resp. topological minor). We are interested in the parameterized complexity of both problems when the parameter is the treewidth of G, denoted by    tw   , and specifically in the cases where    F    contains a single connected planar graph H. We present algorithms running in time      2    O  (   tw   )    xe2x8bx85    n    O  (  1  )     , called singleexponential, when H is either      P    3     ,      P    4     ,      C    4     , the  paw , the  chair , and the  banner  for both      H      MDeletion  and      H      TMDeletion , and when    H      K    1  ,  i     , with    i  xe2x89xa5  1   , for      H      TMDeletion . Some of these algorithms use the rankbased approach introduced by Bodlaender et al. (2015)  7 . This is the second of a series of articles on this topic, and the results given here together with other ones allow us, in particular, to provide a tight dichotomy on the complexity of      H      MDeletion  in terms of H.