# Width, Depth, and Space: Tradeoffs between Branching and Dynamic Programming
## 3 Myhill-Nerode Families
Our goal is to show a lower bound that is logarithmic in the length of the input times a _double exponential function_ of the size of the bags. For this we need a family of graphs that simultaneously has several properties: (1) Each pair \({}^{\circ}\!G_{1}\
eq{}^{\circ}\!G_{2}\) from the family are not equivalent in the sense of a Myhill-Nerode equivalence, i.e., there must be a graph \({}^{\circ}\!H\) such that \({}^{\circ}\!G_{1}\oplus{}^{\circ}\!H\) and \({}^{\circ}\!G_{2}\oplus{}^{\circ}\!H\) give different results, e.g., one is three colorable and the other is not. (2) The family has to be very big because its size is a lower bound on the index of the Myhill-Nerode relation. To show that we need at least \(c^{k}g(n)\) space, the size has to be at least \(2^{c^{k}g(n)}\). If, for example, we want to show that \((3-\epsilon)^{k}\log^{O(1)}(n)\) space is not sufficient, the family has to have size at least \(2^{(3-\epsilon)^{k}\log^{O(1)}(n)}<2^{3^{k}}\). (3) All graphs in the family and \(H\) have to be small. Otherwise \(2^{(3-\epsilon)^{k}\log^{O(1)}(n)}\) could be bigger than \(2^{3^{k}}\). The size \(n\) is the size of a graph from the family glued to \(H\). The following notion of a _Myhill-Nerode family_ will provide us with the machinery to prove space lower-bounds for DPTMs where the input instance is an unlabeled graph and hence for common dynamic programming algorithms on such instances. Recall that \(\lx@overaccentset{{\circ}}{\mathcal{G}}_{s}\) denotes the class of all \(s\)-boundaried graphs. **Definition 3** (Myhill-Nerode family). : _A set \(\mathcal{H}\subseteq\lx@overaccentset{{\circ}}{\mathcal{G}}_{s} \times\mathbf{N}\) is an \(s\)-Myhill-Nerode family for a DP-decision problem \(\Pi_{\mathrm{DP}}\) if the following holds:_  
1. _For every_ \((\lx@overaccentset{{\circ}}{H},q)\in\mathcal{H}\) _it holds that_ \(|\lx@overaccentset{{\circ}}{\mathcal{H}}|=|\mathcal{H}|\cdot \log^{\mathcal{O}(1)}|\mathcal{H}|\) _and_ \(q=2^{|\mathcal{H}|\cdot\log^{\mathcal{O}(1)}|\mathcal{H}|}\)_._
2. _For every subset_ \(\mathcal{I}\subseteq\mathcal{H}\) _there exists an_ \(s\)_-boundaried graph_ \(\lx@overaccentset{{\circ}}{\mathcal{G}}_{\mathcal{I}}\in\lx@overaccentset{{ \circ}}{\mathcal{G}}_{s}\) _with_ \(|\lx@overaccentset{{\circ}}{\mathcal{G}}_{\mathcal{I}}|=| \mathcal{H}|\cdot\log^{\mathcal{O}(1)}|\mathcal{H}|\) _and an integer_ \(p_{\mathcal{I}}\) _such that for every_ \((\lx@overaccentset{{\circ}}{\mathcal{H}},q)\in\mathcal{H}\) _it holds that_ \[(\lx@overaccentset{{\circ}}{\mathcal{G}}_{\mathcal{I}}\oplus \lx@overaccentset{{\circ}}{\mathcal{H}},p_{\mathcal{I}}+q)\
ot\in \Pi_{\mathrm{DP}}\iff(\lx@overaccentset{{\circ}}{\mathcal{H}},q) \in\mathcal{I}.\]  
Let \(\lx@overaccentset{{\circ}}{\mathbf{t}}\mathbf{d}(\lx@overaccentset{{ \circ}}{\mathcal{G}})\) be the minimal depth over all treedepth decompositions of \(\lx@overaccentset{{\circ}}{\mathcal{G}}\in\mathcal{G}_{s}\) where the boundary appears as a path starting at the root. We define the _size_ of a Myhill-Nerode family \(\mathcal{H}\) as \(|\mathcal{H}|\), its _treedepth_ as  
\[\mathbf{t}\mathbf{d}(\mathcal{H})=\max_{(\mathcal{H},\cdot)\in\mathcal{H}, \mathcal{I}\subseteq\mathcal{H}}\lx@overaccentset{{\circ}}{\mathbf{t} }\mathbf{d}(\lx@overaccentset{{\circ}}{\mathcal{G}}_{\mathcal{I}} \oplus\lx@overaccentset{{\circ}}{\mathcal{H}})\]  
and its _treewidth_ and _pathwidth_ as the maximum tree/path decomposition of lowest width of any \((\lx@overaccentset{{\circ}}{\mathcal{H}},\cdot)\in\mathcal{H}\) where the boundary is contained in every bag. The following lemma still holds if we replace \"treedepth\" by \"pathwidth\" or \"treewidth\". **Lemma 1**. : _Let \(\epsilon>0,c>1\) and \(\Pi\) be a DP decision problem such that for every \(s\) there exists an \(s\)-Myhill-Nerode family \(\mathcal{H}\) for \(\Pi\) of size \(c^{s}/f(s)\) where \(f(s)=s^{O(1)}\) and depth \(\mathbf{t}\mathbf{d}(\mathcal{H})=s+o(s)\).