# Width, Depth, and Space: Tradeoffs between Branching and Dynamic Programming
## 6 Fast Dominating Set Using \(O(2^{d}d\log d+d\log n)\) Space
This is exactly what is computed in lines 2-5. Assume now that \(x\) is an internal, non-root node of \(T\). First, in lines 8-13 we assume that \(x\) is not in the dominating set. By inductive assumption calling _domset_ on a child \(y\) of \(x\) returns a table which contains the cost of dominating \(T_{y}\) and some set \(S\subseteq P_{y}\setminus D\). By convoluting them all together \(M_{1}\) represents a function which gives the cost of dominating some set \(S\subseteq(P_{x}\cup\{x\})\setminus D\) and all subtrees rooted at children of \(x\). We just need to take care that \(x\) is dominated. If \(x\) is not dominated by a node in \(D\), then it must be dominated from one of the subtrees. Thus, we are only allowed to retain solutions which dominate \(x\) from the subtrees. We take care of this on line 13. After this \(M_{1}\) represents a function which gives the cost of dominating some set \(S\subseteq(P_{x}\cup\{x\})\setminus D\) and \(T_{x}\) assuming \(x\) is not in the dominating set. Then we compute a solution assuming \(x\) is in the dominating set in lines 14-18. We first merge the results on calls to the children of \(x\) via convolution. Since we took \(x\) into the dominating set we increase the cost of all entries by one. After this \(M_{2}\) represents the function which gives the cost of dominating some set \(S\subseteq P_{x}\setminus D\) and \(T_{x}\) assuming \(x\) is in the dominating set. We finally merge \(M_{1}\) and \(M_{2}\) by taking the minimums. Since we have taken care that all solutions represented by entries in \(M\) dominate \(x\) we can remove all information about \(x\). We do this in lines 21-22. Finally, \(M\) represents the desired function and we return it. When \(x\) is the root, instead of returning the table we return the value for the only entry in \(M\), which is precisely the size of a minimum dominating set of \(G\). To prove the running time of Algorithm 2 we will need the values \(M\) to be all smaller or equal to the depth of \(T\). Thus, we first prove the space upper bound. In the following we treat the associative arrays \(M\), \(M_{1}\) and \(M_{2}\) as if the entries where values between \(0\) and \(n\). We will show that we can represent all values as an offset \(\leq d\) of a single single value between \(0\) and \(n\). Lemma 6: _Algorithm 2 uses \(O(2^{d}d\log d+d\log n)\) bits of space._  
Proof: Let \(d\) be the depth of the provided treedepth decomposition. It is clear that the depth of the recursion is at most \(d\). Any call to the function keeps a constant number of associative arrays and nodes of the graph in memory. By construction these associative arrays have at most \(2^{d}\) entries. For any of the computed arrays \(M\) the value of \(M[\varnothing]\) and \(M[S]\) for any \(S\
eq\varnothing\) can only differ by at most \(d\). We can thus represent every entry for such a set \(S\) as an offset from \(M[\varnothing]\) and use \(O(2^{d}\log d+\log n)\) space for the tables. This together with the bound on the recursion depth gives the bound \(O(2^{d}d\log d+d\log n)\). Lemma 7: _Algorithm 2 runs in time \(O(3^{d}\log d\cdot n)\)._  
Proof: On a call on which \(d^{\prime}\) nodes of \(P_{x}\) are in the dominating set the associative arrays have at most \(2^{s}\) entries for \(s=d-d^{\prime}\). As shown above the entries in the arrays are \(\leq s\) (except one). Hence, we can use fast subset convolution to merge the arrays in time \(O(2^{s}\log s)\)[39]. It follows that the total running time is bounded by  
\[O\big{(}n\cdot\sum_{i=0}^{d}\binom{d}{i}\cdot 2^{d-i}\log(d-i)\big{)}=O(3^{d} \log d\cdot n)\]  
and thus the lemma follows.