# On the Descriptive Complexity of Color Coding +
## 4 Syntactic Proofs and Natural Problems
### Bounded Strong-Rank Description of Embedding Graphs of Constant Tree Width or Constant Tree Depth  
For our final example, a graph \(H=(V(H),E(H))\) embeds into another graph \(G=(V(G),E(G))\) if there is an injective mapping \(\iota\colon V(H)\to V(G)\) such that for all \((u,v)\in E(H)\) we have \((\iota(u),\iota(v))\in E(G)\). We wish to show that the embedding problems for graphs of bounded tree depth or bounded tree width, parameterized by the to-be-embedded graphs, lie in para-AC\({}^{0}\) and para-AC\({}^{0\uparrow}\), see Theorem 8 below. Let us first briefly review the underlying definitions. A tree decomposition of \(H\) is a tree \(T=(V(T),E(T))\) (a connected, acyclic, undirected graph) together with a mapping \(B\) that assigns a subset of \(V(H)\) to each node in \(V(T)\). These subsets are called bags and must have two properties: First, for every edge \(\{u,v\}\in E(H)\) there must be a node \(n\in V(T)\) with \(u,v\in B(n)\). Second, for each vertex \(v\in V(H)\) the set \(\{n\in V(T)\mid v\in B(n)\}\) must be nonempty and connected in \(T\). Let \(\text{width}(B)=\max_{n\in V(T)}|B(n)|-1\). The tree width \(\text{tw}(H)\) of \(H\) is the minimum width of any tree decomposition for it. We call \((T,B)\) a tree-depth decomposition if \(T\) can be rooted in such a way that if \(u\) lies on the path from some vertex \(v\) to the root, then \(B(u)\subsetneq B(v)\). The tree depth \(\text{td}(H)\) is the minimum width of a tree-depth decomposition \((T,B)\) of \(H\) plus 1. Note that this width is an upper bound on \(\text{depth}(T)\), the depth of \(T\), and that this definition is slightly different from the one briefly mentioned in the introduction (but gives the same class). The problems \(\text{p}_{H}\text{-}\text{EMB}_{\text{td}(H)\leq c}\) and \(\text{p}_{H}\text{-}\text{EMB}_{\text{tw}(H)\leq c}\), for a fixed number \(c\) (not a parameter), contains all pairs \((G,\text{num}(H))\in\textsc{struc}[(E^{2})]\times\mathbb{N}\) such that there exists an embedding of \(H\) into \(G\) and \(\text{td}(H)\leq c\) and \(\text{tw}(H)\leq c\), respectively. Theorem 8 ([6,7]): \(\text{p}_{H}\text{-}\text{EMB}_{\text{td}(H)\leq c}\in\text{para-AC}^{0}\) _and \(\text{p}_{H}\text{-}\text{EMB}_{\text{tw}(H)\leq c}\in\text{para-AC}^{0\uparrow}\) for each \(c\)._  
Proof: We present a family \((\phi_{H,T,B})\) of \(\tau\)-formulas (where \(\tau=(E^{2},<^{2},\textsc{succ}^{1},\textsc{add}^{3},\textsc{mult}^{3},0^{0})\) is the arithmetic signature of graphs) indexed by graphs \(H\) together with any tree decomposition \((T,B)\) of \(H\) (without bounds on the depth or width) that describe the embedding problem. More precisely, we show the following:  
Claim 5: _There is a family \((\phi_{H,T,B})_{H}\in\textsc{struc}[\tau]\),\((T,B)\) is a tree decomposition of \(H\) such that:_  
1. \(\mathcal{G}\models\phi_{H,T,B}\) _if and only if_ \(H\) _embeds into_ \(\mathcal{G}\) _(more precisely, into_ \((|\mathcal{G}|,E^{\mathcal{G}})\)_)._
2. \(\text{strong-}\text{\rm qr}(\phi_{H,T,B})=\text{depth}(T)\)_._
3. \(|\text{strong-bound}(\phi_{H,T,B})|=\text{width}(B)+1\)_._  
Proof: Before we present the formula, we define what we will call a consistent numbering of the vertices of \(H\). It is a mapping \(p\colon V(H)\to\{1,\ldots,m\}\), where \(m\) is the maximum bag size of the decomposition (so \(m=\text{width}(B)+1\)). The number \(p(v)\) for \(v\in V(H)\) can be thought as the \"position\" or \"index\" of \(v\) in all bags that contain it, that is, we require that for any bag \(B(n)=\{b_{1},\ldots,b_{|B(n)|}\}\) the values \(p(b_{1}),\ldots,p(b_{|B(n)|})\) are all different. (Phrased differently, \(p\) restricted to any bag is injective.) Such a consistent numbering can be obtained as follows: First, assign the numbers \(1\) to \(|B(r)|\) to the elements of the root bag \(B(r)\). Now, consider a child \(c\) of the root \(r\) in \(T\). The bag \(B(c)\) may miss some of the elements of \(B(r)\) and there may be some new elements.