# Width, Depth, and Space: Tradeoffs between Branching and Dynamic Programming
## 1 Introduction
To formalize the notion of a dynamic programming algorithm on tree, path and treedepth decompositions, we consider algorithms that take as input a tree-, path- or treedepth decomposition of width/depth \(s\) and size \(n\) and satisfy the following constraints:  
1. They pass a _single time_ over the decomposition in a bottom-up fashion;
2. they use \(O(f(s)\cdot\log^{O(1)}n)\) space; and
3. they do not modify the decomposition, including re-arranging it. While these three constraints might look stringent, they include pretty much all dynamic programming algorithm for hard optimization problems on tree or path decompositions. For that reason, we will refer to this type of algorithms simply as _DP algorithms_ in the following. To show the aforementioned space lower bounds, we introduce a simple machine model that models DP algorithms on treedepth decompositions and construct superexponentially large _Myhill-Nerode families_ that imply lower bounds for Dominating Set, Vertex Cover/Independent Set and 3-Colorability in this algorithmic model. These lower bounds hold as well for tree and path decompositions and align nicely with the space complexity of known DP algorithms: for every \(\epsilon>0\), no DP algorithm on such decomposition of width/depth \(d\) can use space bounded by \((3-\epsilon)^{d}\cdot\log^{O(1)}n\) for 3-coloring or Dominating Set nor \((2-\epsilon)^{d}\cdot\log^{O(1)}n\) for Vertex Cover/Independent Set. While probably not surprising, we consider a formal proof for what previously were just widely held assumptions valuable. The provided framework should easily extend to other problems. Consequently, any algorithmic benefit of treedepth over pathwidth and treewidth must be obtained by non-DP means. We demonstrate that treedepth allows the design of branching algorithms whose space consumption grows only polynomially in the treedepth and logarithmic in the input size. Such space-efficient algorithms are quite easy to obtain for 3-Coloring and Vertex Cover/Independent Set with running time \(O(3^{d}\cdot n)\) and \(O(2^{d}\cdot n)\), respectively, and space complexity \(O(d+\log n)\) and \(O(d\cdot\log n)\). Our main contribution on the positive side here are two linear-fpt algorithms for Dominating Set which use more involved branching rules on treedepth decompositions. The first one runs in time \(d^{O(d^{2})}\cdot n\) and uses space \(O(d^{3}\log d+d\cdot\log n)\). Comparedto simple dynamic programming, the space consumption is improved considerably, albeit at the cost of a much higher running time. For this reason, we design a second algorithm that uses a hybrid approach of branching and dynamic programming, resulting in a competitive running time of \(O(3^{d}\log d\cdot n)\) and space consumption \(O(2^{d}d\log d+d\log n)\). Both algorithms are amenable to heuristic improvements. While applying branching to treedepth seems natural, it is unclear whether it could be applied to treewidth or pathwidth. Recent work by [PERSON], [PERSON] and [PERSON] suggests that, relative to a collapse of the polynomial hierarchy, Independent Set restricted to low-pathwidth graphs cannot be solved by a branching algorithm in fpt time [34]. The idea of using treedepth to improve space consumption is not novel. [PERSON] and [PERSON] demonstrated that it is possible to count matchings using polynomial space in the size of the input [17] and a parameter closely related to the treedepth of the input. Their algorithm achieves a small memory footprint by using the algebraization framework developed by [PERSON] and [PERSON] [35]. This technique was also used by [PERSON] and [PERSON] to develop an algorithm for Dominating Set which runs in time \(3^{d}\cdot\operatorname{poly}(n)\) (non-linear) and uses space \(O(d\cdot\log n)\)[36]. Based on this last algorithm they showed that computations on treedepth 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.