# On the Descriptive Complexity of Color Coding +
###### Abstract
[4], stated as Fact 1 in our paper: Our new Theorem 1 states that a parameterized problem can be described slicewise by a family \((\phi_{k})_{k\in\mathbb{N}}\) of arithmetic first-order formulas that all use only a bounded number of variables if and only if the problem lies in para-AC\({}^{0\dagger}\)--a class that has been encountered repeatedly in the literature [5; 7; 8; 9], but for which no characterization was known. It contains all parameterized problems that can be decided by AC-circuits whose depth depends only on the parameter and whose size is of the form \(f(k)\cdot n^{c}\). As an example, consider the problem of deciding whether a graph contains a path of length \(k\) (no vertex may be visited twice). It can be described by the family \((\delta_{k})\) of formulas with (for odd \(k\)) \(\delta_{k}\) equal to  
\[\exists s\exists\dot{n}\exists x(E\!sx\wedge\exists\dot{x}_{1}( \dot{x}_{1}=x\wedge\] \[\exists y(E\!sx\wedge\exists\dot{x}_{2}(\dot{x}_{2}=y\wedge\] \[\exists x(E\!sx\wedge\exists\dot{x}_{3}(\dot{x}_{3}=x\wedge\] \[\exists y(E\!sx\wedge\exists\dot{x}_{4}(\dot{x}_{4}=y\wedge\] \[\beta_{k} =\exists x_{1}\cdots\exists x_{3k}\big{(}\bigwedge_{i\
eq j}x_{i} \
eq x_{j}\wedge\bigwedge_{i=1}^{k}(Ex_{3i-2}x_{3i-1}\wedge Ex_{3i-2}x_{3i} \wedge Ex_{3i-1}x_{3i})\big{)},\]0  
Note that the strong quantifier rank of \(\delta_{k}\) is \(k+2\) and, thus, depends on \(k\). However, there are only four strong variables, namely \(s\), \(t\), \(x\), and \(y\). By Theorem 3 we see that the above formulas are equivalent to a family of formulas with a bounded number of variables and by Theorem 1 we see that \(\mathfrak{p}_{k}\)-long-path\(\in\) para-AC\({}^{0\dagger}\subseteq\) FPT. These ideas also generalize easily and we give a purely syntactic proof of the seminal result from the original color coding paper [3] that the embedding problem for graphs of bounded tree width lies in FPT. The core observation--which unifies the results for tree width and depth--is that for each graph with a given tree decomposition, the embedding problem can be described by a formula whose strong nesting structure mirrors the tree structure and whose strong variables mirror the bag contents. Table 1 summarizes, for the problems discussed in this paper, how they can be described using formulas in such a way that membership in para-AC\({}^{0}\) and para-AC\({}^{0\dagger}\) follows. All memberships were previously known, the contribution of this paper is that we prove the memberships by presenting families of first-order formulas that describe them, such that that strong quantifier rank (strong-qr) or the number of strong variables (strong-vars) is parameter-independent. \begin{table}
\begin{tabular}{l} \hline \hline \(\text{P}_{k}\text{-matching}\in\text{para-AC}^{0}\) \\ Problem: Does a graph have a size-\(k\) matching? \\ Formulas: \(\exists\hat{x}_{1}\cdots\exists\hat{x}_{2k}\big{(}\bigwedge_{i\
eq j}\hat{x}_{i} \
eq\hat{x}_{j}\wedge\bigwedge_{i=1}^{k}E\hat{x}_{2i-1}\hat{x}_{2i}\big{)}\), see Equation (1) \\ Descriptive complexity: strong-qr = 0, strong-vars = 0 \\ \(\text{P}_{k}\text{-}\text{triangle-packing}\in\text{para-AC}^{0}\) \\ Problem: Does a graph contain \(k\) vertex-disjoint triangles? \\ Formulas: \(\exists\hat{x}_{1}\cdots\exists\hat{x}_{3k}\big{(}\bigwedge_{i\
eq j}\hat{x}_{i }\
eq\hat{x}_{j}\wedge\bigwedge_{j=1}^{k}\exists x\exists y\exists\exists z\) ( \\ \(\hat{x}_{3j-2}=x\wedge x_{3j-1}=y\wedge x_{3j}=z\wedge Exy\wedge Exz\wedge Eyz)\big{)}\), see Equation (2) \\ Descriptive complexity: strong-qr = 3, strong-vars = 3 \\ \(\text{P}_{k}\text{-}\text{H-packing}\in\text{para-AC}^{0}\) for a fixed graph \(H=(V(H),E(H))\) (instead of triangles) \\ Problem: Does a graph contain \(k\) vertex-disjoint induced copies of \(H\)?