# 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  
We have seen that it is possible to solve Dominating Set on low-treedepth graphs in a space-efficient manner. However, we traded space exponential in the treedepth against superexponential running time in the treedepth and it is natural to ask whether there is some middle ground. We present Algorithm 2 to answer this question: its running time \(O(3^{d}\log d\cdot n)\) is competitive with the default dynamic programming but its space complexity \(O(2^{d}\log d+d\log n)\) is exponentially better. The basic idea is to again branch from the top deciding if the current node \(x\) is in the dominating set or not. Intertwined in this branching we compute a function which for a subtree \(T_{x}\) and a set \(S\subseteq P_{x}\) gives the cost of dominating \(V(T_{x})\cup S\) from \(T_{x}\). For each recursive call on a node we only need this function for subsets of \(P_{x}\) which are not dominated. If \(d^{\prime}\) is the number of nodes of \(P_{x}\) that are currently contained in \(D\), the function only needs to be computed for \(2^{d-d^{\prime}}\) sets. This allows us to keep the running time of \(O^{*}(3^{d})\), since \(\sum_{i=0}^{d}{{i}\choose{i}}\cdot 2^{d-i}=3^{d}\), while only creating tables with at most \(O(2^{d})\)entries. By representing all values in these tables as \(\leq d\) offsets from a base value, the space bound \(O(2^{d}d\log d+d\log n)\) follows. Part of the algorithm will be _convolution_ operations. Definition 4 (Convolution): For two functions \(M_{1},M_{2}\) with domain \(2^{U}\) for some ground-set \(U\) we use the notation \(M_{1}*M_{2}\) to denote the _convolution_\((M_{1}*M_{2})[X]:=\min_{A\uplus B=X}M_{1}[A]+M_{2}[B]\), for all \(X\subseteq U\). ```
Input: A graph \(G\), a treedepth decomposition \(T\) of \(G\), a node \(x\) of \(T\) and a set \(D\subseteq V(G)\). Output: The size of a minimum Dominating Set if \(x\) is the root of \(T\) and \(D=\emptyset\). 1\(M,M_{1},M_{2}:=\) are empty associative arrays. If a set is not in the array its value is \(\infty\);
2 if\(x\) is a leaf in \(T\)then
3 foreach\(S\subseteq(P_{x}\cap N_{G}[X])\setminus D\)do\(M[S]:=1\);
4 if\(x\in N_{G}[D]\)then\(M[\varnothing]:=0\) ;
5 return\(M\);
6
7 end if
8
9/* Assume the children of \(x\) are \(\{y_{1},\ldots,y_{\ell}\}\). */
10 for\(i\in\{1,\ldots,\ell\}\)do
11\(M^{\prime}:=\)\(\operatorname{domset}(G,T,y_{i},D)\);
12\(M_{1}:=M_{1}*M^{\prime}\);
13
14 end for
15/* \(x\) is not in the dominating set. Discard entries where \(x\) is undominated. */
16 if\(x\
otin N_{G}[D]\)then delete all entries \(S\) from \(M_{1}\) where \(x\
otin S\) ;
17 for\(i\in\{1,\ldots,\ell\}\)do
18\(M^{\prime}:=\)\(\operatorname{domset}(G,T,y_{i},D\cup\{x\})\);
19\(M_{2}:=M_{2}*M^{\prime}\);
20
21 end for
22 foreach\(S\in M_{2}\)do\(M_{2}[S]:=M_{2}[S]+1\) ;
23 foreach\(S\subseteq P_{x}\)do\(M[S]:=\min\{M_{1}[S],M_{2}[S]\}\);
24/* Forget \(x\). */
25 foreach\(S\in M\) where \(x\
otin S\)do\(M[S]:=min(M[S],M[S\cup\{x\}])\) ;
26 Delete all entries \(S\) from \(M\) where \(x\in S\);
27 if\(x\) is the root of \(T\)thenreturn\(M[\varnothing]\) ;
28
29 elsereturn\(M\) ;
```  
**Algorithm 2**Computing dominating sets with \(O^{*}(2^{d})\) space. We divide the proof into lemmas as before. Lemma 5: Algorithm 2 _called on \(G,T,r,\emptyset\), where \(T\) is a treedepth decomposition of \(G\) with root \(r\), returns the size of a minimum dominating set of \(G\)._  
Proof: Notice that the associative array \(M\) represents a function which maps subsets of \(P_{x}\setminus D\) to integers and \(\infty\). At the end of any recursive call, \(M[S]\) for \(S\subseteq P_{x}\setminus D\) should be the size of a minimal dominating set in \(T_{x}\) which dominates \(T_{x}\) and \(S\) assuming that the nodes in \(D\) are part of the dominating set. We will prove this inductively. Assume \(x\) is a leaf. We can always take \(x\) into the dominating set at cost one. In case \(x\) is already dominated we have the option of not taking it, dominating nothing at zero cost.