# Width, Depth, and Space: Tradeoffs between Branching and Dynamic Programming
## 4 Space Lower Bounds for Dynamic Programming
Imagine branching on the topmost vertex of the decomposition: while the branch that includes the vertex into the dominating set produces a straightforward recurrence into annotated instances, the branch that excludes it from the dominating set needs to decide _how_ that vertex should be dominated. The algorithm we present here proceeds as follows: We first guess whether the current node \(x\) is in the dominating set or not. Recall that \(P_{x}\) denotes the nodes of the decomposition that lie on the unique path from \(x\) to the root of the decomposition (and \(x\
ot\in P_{x}\)). We iterate over every possible partition \(S_{1}\uplus\cdots\uplus S_{\ell}=P_{x}\cup\{x\}\) into \(\ell\leq d\) sets of \(P_{x}\cup\{x\}\). The semantic of a block \(S_{i}\) is that we want every element \(S_{i}\) to be dominated exclusively by nodes from a specific subtree of \(x\). A recursive call on a child \(y\) of \(x\), together with an element of the partition \(S_{i}\), will return the size of a dominating set which dominates \(V(T_{y})\cup S_{i}\). The remaining issue is how these specific solutions for the subtrees of \(x\) can be combined into a solution in a space-efficient manner. To that end, we first compute the size of a dominating set for \(T_{y}\) itself and use this as baseline cost for a subtree \(T_{y}\). For a block \(S_{i}\) of a partition of \(P_{x}\), we can now compare the cost of dominating \(V(T_{y})\cup S_{i}\) against this baseline to obtain overhead cost of dominating \(S_{i}\) using vertices from \(T_{y}\). Collecting these overhead costs in a table for subtrees of \(x\) and the current partition, we are able to apply certain reduction rules on these tables to reduce their size to at most \(d^{2}\) entries. Recursively choosing the best partition then yields the solution size using only polynomial space in \(d\) and logarithmic in \(n\). Formally, we prove the following:  
Theorem 4.2: _Given a graph \(G\) and a treedepth decomposition \(T\) of \(G\), Algorithm 1 finds the size of a minimum dominating set of \(G\) in time \(d^{O(d^{2})}\cdot n\) using \(O(d^{3}\log d+d\log n)\) bits._  
We split the proof of Theorem 4.2 into lemmas for correctness, running time and used space. Lemma 2: _Algorithm 1 called on a graph \(G\), a treedepth decomposition \(T\) of \(G\), the root \(r\) of \(T\) and \(P=D=\varnothing\) returns the size of a minimum dominating set of \(G\)._  
Proof: If we look at a minimal dominating set \(S\) of \(G\) we can charge every node in \(V(G)\setminus S\) to a node from \(S\) that dominates it. We are thus allowed to treat any node in \(G\) as if it was dominated by a single node of \(S\). We will prove this lemma by induction, the inductive hypothesis being that a call on a node \(x\) with arguments \(D=S\cap P_{x}\) and \(P\subseteq P_{x}\) being the set of nodes dominated from nodes in \(T_{x}\) by \(S\) returns \(|S\cap V(T_{x})|\). It is clear that the algorithm will call itself until a leaf is reached. Let \(x\) be a leaf of \(T\) on which the function was called. We first check the condition at line 2, which is true if either \(x\) is not dominated by a node in \(D\) or if some node in \(P\) is not yet dominated. In this case we have no choice but to add \(x\) to the dominating set. Three things can happen: \(P\) is not fully dominated, which means that it was not possible under these conditions to dominate \(P\), in which case we correctly return \(\infty\), signifying that there is no valid solution. Otherwise we can assume \(P\) is dominated and we return \(1\) if we had to take \(x\) and \(0\) if we did not need to do so. Thus, the leaf case is correct. We assume now \(x\) is not a leaf and thus we reach line 7. We first add \(x\) to \(P\), since it can only be dominated either from a node in \(D\) or a node in \(T_{x}\). Nodes in \(T_{x}\) can only be dominated by nodes from \(V(T_{x})\cup P_{x}\). We assume by induction that \(D=S\cap P_{x}\) and that \(P\) only contains nodes which are either in \(S\) or dominated from nodes in \(T_{x}\).