# On the Descriptive Complexity of Color Coding +
## 4 Syntactic Proofs and Natural Problems
### Bounded Strong-Rank Description of Hitting Set  
Hitting sets generalize vertex covers to hypergraphs, which are pairs \((V,E)\) where the members of \(E\) are called hyperedges and we have \(e\subseteq V\) for all \(e\in E\). Hitting sets are still sets \(X\subseteq V\) with \(e\cap X\
eq\emptyset\) for all \(e\in E\). The problem \(\mathrm{p}_{k,d}\textsc{-}\textsc{Hitting-}\textsc{set}\) asks whether a hypergraph with \(\max_{e\in E}|e|\leq d\) has a hitting set \(X\) with \(|X|\leq k\). Formally, let \(d(H)\) be the maximum size of any hyperedge in \(H\) and \(\mathrm{p}_{k,d}\textsc{-}\textsc{Hitting-}\textsc{set}\) be the set of all pairs \((\mathcal{H},\max(k,d))\) such that \(\mathcal{H}\) encodes (see below for details) a hypergraph \(H\) with \(d(H)\leq d\) and for which there is a hitting set of size at most \(k\). The problem \(\mathrm{p}_{k}\textsc{-}\textsc{vertex-}\textsc{cover}\) is basically this problem restricted to the parameter value \(d=2\) (if one models size-1 hyperedges \(e\) as self-loops and ignores the case of the empty hyperedge, which can never be hit by any set \(X\)). While by no means trivial, it is not too hard to generalize the arguments used in Theorem 5 to prove that the parameterized hitting sets problem lies in para-AC\({}^{0}\) when \(d\) is fixed and \(k\) is the parameter. It is much harder to prove the following result, where both \(d\) and \(k\) are parameters:  
Theorem 6 ([19]): \(\mathrm{p}_{k,d}\textsc{-}\textsc{Hitting-}\textsc{set}\in\mathrm{para-AC}^{0}\)_._  
Before we prove the theorem using our framework, we need to fix how we model hypergraphs \((V,E)\) as logical structures. We use a \(\tau_{\textsc{hyper}}\)-structure \(\mathcal{H}\) for \(\tau_{\textsc{hyper}}=(\textsc{vertex}^{1}\), \(\textsc{hyperedge}^{1},\textsc{IN}^{2})\). Let \(|\mathcal{H}|=V\cup E\), \(\textsc{vertex}^{\mathcal{H}}=V\), set \(\textsc{hyperedge}^{\mathcal{H}}=E\), and \(\textsc{in}^{\mathcal{H}}=\{(v,e)\mid v\in e\in E\}\). The other way round, given a \(\tau_{\textsc{hyper}}\)-structure \(\mathcal{H}\), we consider it as the following hypergraph \(H(\mathcal{H})=(V,E)\) with \(V=\textsc{vertex}^{\mathcal{H}}\) and \(E=\{\mathrm{set}(e)\mid e\in\textsc{hyperedge}^{\mathcal{H}}\}\), where we write \(\mathrm{set}(e)\) for \(\{v\mid(v,e)\in\textsc{in}^{\mathcal{H}}\}\). Note that we allow the universe of \(\mathcal{H}\) to contain elements \(e\) that are neither vertices nor hyperedge-representing elements, but their \(\mathrm{set}(e)\) do not contribute to \(E\). We also allow that two different elements \(e,e^{\prime}\in|\mathcal{H}|\) represent the same set \(\mathrm{set}(e)=\mathrm{set}(e^{\prime})\). This can be problematic in a kernelization: When we identify a kernel set \(E^{\prime}\) of hyperedges, there could still be a large (non-parameter-dependent) number of elements in the universe that represent these hyperedges--meaning that these elements do not form a kernel themselves. Fortunately, this can be fixed: We can easily check whether two elements represent the same set using \(\forall x(\textsc{in}\,xe\leftrightarrow\textsc{in}\,xe^{\prime})\) and then always consider only the first representing element with respect to the ordering \(<\) of the universe. For this reason, we will assume in the following that for any subset \(s\subseteq V\) there is at most one \(e\in|\mathcal{H}|\) with \(s=\mathrm{set}(e)\). Proof of Theorem 6.: The idea behind the proof is a (very strong) generalization of the Buss kernel argument from the proof of Theorem 5. As in that proof, we will present a family \((\phi_{k,d}),k_{d,k\in\mathbb{N}}\) of bounded strong quantifier rank that describes \(\mathrm{p}_{k,d}\textsc{-}\textsc{Hitting-}\textsc{set}\). First, there are two simple preliminaries: Testing whether \(d(\mathcal{H})\leq d\) holds is easy to achieve using \(\forall e(\textsc{hyperedge}\leftarrow\exists^{\leq d}v(\textsc{in}\,ve))\), so let us assume that this is the case and let us write \(H=(V,E)\) for \(H(\mathcal{H})\).