# Width, Depth, and Space: Tradeoffs between Branching and Dynamic Programming
## 4 Space Lower Bounds for Dynamic Programming
For every set \(D\in\mathcal{D}_{W}\) we construct the gadget \(\prescript{\circ}{}{\Lambda}_{D}\) by arbitrarily pairing the vertices in \(D\) and connecting them via the circuit gadget as exemplified in Figure 2. This closely parallels the constructions we have seen in the proofs for Theorem 1 and 2: If \(|D|\) is odd, we pair some vertex of \(D\) with itself. We then repeat the construction with all the \(u\)-vertices of those gadgets, resulting in a hierarchical structure of depth \(\sim\log|D|\). To finalize the construction of \(\prescript{\circ}{}{\Lambda}_{D}\) we take the \(u\)-vertex of the last layer and connect it to a new vertex \(u^{\prime}\). This concludes the construction of \(\prescript{\circ}{}{\Lambda}_{D}\). Let in the following \(\lambda\) be the number of circuits we used to construct such a \(\prescript{\circ}{}{\Lambda}_{D}\) gadget (this quantity only depends on \(s\) and is the same for any \(\prescript{\circ}{}{\Lambda}_{D}\)). If \(\mathcal{D}_{W}\) is empty, then \(\mathrm{T}_{W}\) is the boundary and a \(K_{2}\) with one of its vertices connected to all vertices in \(W\) plus \(\binom{2s/3}{s/3}2\lambda\) isolated padding-vertices. Otherwise we obtain \(\mathrm{T}_{W}\) by taking the graph \(\bigoplus_{D\in\mathcal{D}}\prescript{\circ}{}{\Lambda}_{D}\) and adding two additional vertices \(a,b\) as well as \(\big{(}\binom{2s/3}{s/3}-|\mathcal{D}_{W}|\big{)}2\lambda\) isolated vertices for padding. The vertex \(a\) is connected to all \(u^{\prime}\) vertices of all the gadgets \(\{\prescript{\circ}{}{\Lambda}_{D}\}_{D\in\mathcal{D}_{W}}\) and the vertex \(b\) is connected to \(\{a\}\cup W\) (c.f., again Figure 2 for an example). Finally we define for every \(\mathcal{I}\subseteq\mathcal{H}\) the graph \(\prescript{\circ}{}{G}_{\mathcal{I}}=\bigoplus_{W\subset X,|W|=s/3}\mathrm{T}_ {W}\). Let \(\alpha=\binom{2s/3}{s/3}2\lambda+1\). Consider some \(\mathrm{T}_{W}\), for a \(W\) such that \(\mathcal{D}_{W}\
eq\varnothing\). Assume we start with a dominating set \(S\) such that \(S\cap D=\emptyset\) for at least one \(D\in D_{W}\). We want to show that extending \(S\) to dominate \(V((\mathrm{T}_{W})\setminus X)\cup W\) requires at least \(\alpha+1\) many vertices. We can assume that \(b\) must be added to the dominating set. All \(\big{(}\binom{2s/3}{s/3}-|\mathcal{D}_{W}|\big{)}2\lambda\) padding vertices must also be added. Since we need at least two vertices per circuit gadget, at least \(2\lambda\) vertices will always be necessary to dominate each \(\prescript{\circ}{}{\Lambda}_{D}\) subgraph of \(\mathrm{T}_{W}\) (of which there are \(|\mathcal{D}_{W}|\) many). For \(\prescript{\circ}{}{\Lambda}_{D}\) where \(S\cap D=\emptyset\) no dominatingset of the circuit gadgets of size \(2\lambda\) can also dominate \(u^{\prime}\). Thus we also need to take \(a\) or \(u^{\prime}\) into the dominating set and we need at least \(\alpha+1\) many vertices. Now assume that we start with a dominating set \(S\) that contains at least one node of every \(D\in\mathcal{D}_{W}\
eq\varnothing\). In this case we can dominate all the circuit gadgets and \(u^{\prime}\) with \(2\lambda\) many nodes in every \({}^{\circ}\!\Lambda_{D}\). Thus, there is a set in \(\mathrm{T}_{W}\) that dominates \(V((\mathrm{T}_{W})\setminus X)\cup W\) of size \(\alpha\), since neither \(a\) nor any \(u^{\prime}\)  
topmost vertex of the decomposition and recur into (annotated) subinstances. For \(q\)-Coloring, this leads to an algorithm with running time \(O(q^{d}\cdot n)\) and space complexity \(O(d\log n)\). Since it is possible to perform a depth-first traversal of a given tree using only \(O(\log n)\) space [38], the space consumption of this algorithm can be easily improved to \(O(d+\log n)\). Similarly, branching solves Vertex Cover in time \(O(2^{d}\cdot n)\) and space \(O(d\log n)\). The task of designing a similar algorithm for Dominating Set is much more involved.