# Width, Depth, and Space: Tradeoffs between Branching and Dynamic Programming
## 4 Space Lower Bounds for Dynamic Programming
From the previous arguments about the possible vertex covers for the \({}^{\circ}\!T_{A^{\prime}}\) gadgets it follows that the solution still needs two nodes for every circuit gadget of \({}^{\circ}\!T_{A^{\prime}}\), but now this part of the vertex cover can include \(u^{\prime}\). Since this is true for every \({}^{\circ}\!T_{A^{\prime}}\) it follows that \(a\) does not need to be part of the vertex cover. Thus, the size of an optimal vertex cover is precisely \(\ell+s/2-1\). If \({}^{\circ}\!H_{A}\in\mathcal{I}\) then the gadget \({}^{\circ}\!T_{A}\) that has no vertex cover using two nodes per circuit gadget that contains its node \(u^{\prime}\). It follows that any optimal vertex cover of \({}^{\circ}\!G_{\mathcal{I}}\oplus{}^{\circ}\!H_{A}\) must contain either \(a\) or its \(u^{\prime}\). Thus the size of the solution is at least \(\ell+s/2\). We thus set \(p_{\mathcal{I}}\) to be \(\ell-1\). The size of the family \(\mathcal{H}\) is, using [PERSON]'s approximation, bounded from below by  
\[\binom{s}{s/2}\geq\frac{2^{s-1}}{\sqrt{s/2}}\]  
and is smaller than \(2^{s}\). All numbers involved describe subsets of graphs and thus must be smaller than the sizes of those graphs. All graphs in the family have size \(s\). The graphs \(\prescript{\circ}{}{G}_{\mathcal{I}}\) as described, are constructed by adding a polylogarithmic number of nodes to the boundary per gadget \(\mathrm{T}_{A}\) and thus their size is bounded by \(|\mathcal{H}|\cdot\log^{O(1)}|\mathcal{H}|\). For odd \(s\) we take \(s^{\prime}=s-1\) and use the \(s^{\prime}\)-family as the \(s\)-family. The treedepth is \(\mathbf{td}(\mathcal{H})=s+o(s)\) by the same argument as for the construction for Theorem 1. We conclude that \(\mathcal{H}\) is an \(s\)-Myhill-Nerode family of size \(2^{s}/f(s)\) for \(f(s)=s^{O(1)}\cap\Omega(1)\) and depth \(\mathbf{td}(\mathcal{H})=s+o(s)\) and thus by Lemma 1 the theorem follows. For every \(\epsilon>0\), no DPTM solves Dominating Set on a tree, path or treedepth decomposition of width/depth \(k\) with space bounded by \(O\big{(}(3-\epsilon)^{k}\cdot\log^{O(1)}n\big{)}\). Proof. : For any \(s\) divisible by three we construct an \(s\)-Myhill-Nerode family \(\mathcal{H}\) as follows. Let \(X\) be the \(s\) boundary vertices of all the boundaried graphs in the following. Then for every three-partition \(\mathcal{X}=(B,D,W)\) of \(X\) into sets of size \(s/3\), we construct a graph \(H_{\mathcal{X}}\) by connecting two new pendant vertices (with degree one) to every vertex in \(B\), connecting every vertex in \(D\) to a vertex which itself is connected to two pendant vertices and leaving \(W\) untouched and thus isolated. Intuitively, we want the vertices of \(B\) to be in any minimal dominating set, the vertices in \(D\) to be dominated from a vertex in \(H_{\mathcal{X}}\) not in the boundary and the vertices in \(W\) to be dominated from elsewhere. We add every pair \((H_{\mathcal{X}},2s/3)\) to \(\mathcal{H}\). Notice that the size of an optimal dominating set of \(H_{\mathcal{X}}[B\cup D]\) is \(2s/3\) and there is only one such optimal dominating set, namely \(B\cup N(D)\). For a subset \(\mathcal{I}\subseteq\mathcal{H}\) let \(\mathcal{D}_{W}=\{D\mid H_{(X\setminus(D\cup W),D,W)}\in\mathcal{I}\}\) be a set defined for every \(W\subset X\). We construct the graph \(\prescript{\circ}{}{G}_{\mathcal{I}}\) using the _circuit gadget_ with nodes \(v_{1},v_{2},u\) highlighted in Figure 2: Please note that if \(v_{1},v_{2}\) need to be dominated, then there is no dominating set of the gadget of size two that contains \(u\). If one of \(v_{1},v_{2}\) does not need to be dominated (but is not in the dominating set) then a dominating set of size two of the circuit gadget containing \(u\) exists. For every \(W\subset X\) with \(|W|=s/3\) construct a _testing gadget_\(\mathrm{T}_{W}\) as follows. Assume first that \(\mathcal{D}_{W}\) is non-empty.