# Width, Depth, and Space: Tradeoffs between Branching and Dynamic Programming
## 4 Space Lower Bounds for Dynamic Programming
Algorithm 1 executes the same computations for \(D\) and \(D\cup\{x\}\), representing not taking and taking \(x\) into the dominating set respectively. We must show that the set \(P\) for the recursive calls is correct. There exists a partition of the nodes of \(P\) not dominated by \(D\) (respectively \(D\cup\{x\}\)) such that the nodes of every element of the partition are dominated from a single subtree \(T_{y}\) where \(y\) is a child of \(x\). The algorithm will eventually find this partition on line 9. The baseline value, i.e., the size of a dominating set of \(T_{y}\) given that the nodes in \(D\) (respectively \(D\cup\{x\}\)) are in the dominating set, gives a lower bound for any solution. In the lists in \(L\) and \(L^{\prime}\) we keep the extra cost incurred by a subtree \(T_{y}\) if it has to dominate an element of the partition. We only need to keep the best \(d\) values for every \(S_{i}\): Assume that it is optimal to dominate \(S_{i}\) from \(T_{y}\) and there are \(d+1\) subtrees induced on children \(y^{\prime}\
eq y\) of \(x\) whose extra cost over the baseline to dominate \(S_{i}\) is strictly smaller than the extra cost for \(T_{y}\). At least one of these subtrees \(T_{y^{\prime}}\) is not being used to dominate an element of the partition. This means we could improve the solution by letting \(T_{y}\) dominate itself and taking the solution of \(T_{y^{\prime}}\) that also dominates \(S_{i}\). Keeping \(d\) values for every element in the partition suffices to find a minimal solution, which is what \(\mathit{find\_min\_solution}(L)\) does as follows: Create a bipartite graph \(G=(A\uplus B,E)\) such that \(A\) contains a node for every \(S_{i}\) and \(B\) contains a node for every \(y\) for which there is an entry \((\cdot,y)\) in \(L\). For every node \(a\) representing \(S_{i}\) we add an edge with weight \(d-c\) to a node \(b\) representing \(y\) if \((c,y)\in L[i]\). Notice that the minimal number of nodes above the baseline needed to dominate an element of the partition is always less than \(d\). A maximal matching in this bipartite graph tells us how many nodes above the baseline are required to dominate the elements of the partition from subtrees rooted at children of \(x\). Since \(L\) contains at most \(d^{2}\) entries this can be computed in polynomial time in \(d\). Since with lines 27 and 28 we take the minimum over all possible partitions and taking \(x\) into the dominating set or not, we get that by inductive assumption the algorithm returns the correct value. The lemma follows since the first call to the algorithm with \(D=P=\varnothing\) is obviously correct. **Lemma 3**. : _Algorithm 1 runs in time \(d^{O(d^{2})}\cdot n\)._  
Proof. : The running time when \(x\) is a leaf is bounded by \(O(d^{2})\), since all operations exclusively involve some subset of the \(d\) nodes in \(P_{x}\cup\{x\}\). Since \(|P|\leq d\) the number of partitions of \(P\) is bounded by \(d^{d}\). When \(x\) is not a leaf the only time spent on computations which are not recursive calls of the algorithm are all trivially bounded by \(O(d)\), except the time spent on find_min_solution, which can be solved via a matching problem in polynomial time in \(d\) (see proof of Lemma 2). The number of recursive calls that a single call on a node \(x\) makes on a child \(y\) is \(O(d\cdot d^{d})\) which bounds the total number of calls on a single node by \(d^{O(d^{2})}\). This proves the claim. **Lemma 4**. : _Algorithm 1 uses \(O(d^{3}\log d+d\log n)\) bits of space._  
Proof. : There are at most \(d\) recursive calls on the stack at any point. We will show that the space used by one is bounded by \(O(d^{2}\log d+\log n)\). Each call uses \(O(d)\) sets, all of which have size at most \(d\). The elements contained in these sets can be represented by their position in the path to the root of \(T\), thus they use at most \(O(d^{2}\log d)\) space.