# A Brief Survey of Fixed-Parameter Parallelism
## 7 Parallel Algorithms Using FPT Methods
### Color Coding  
It was shown in [17] that an \((n,k,c)\)-universal color coding can be achieved in \(O(log(c)*c^{k^{2}}*k^{4}*log^{2}(n))\) using a polynomial number of processors, by generating a set of hash functions, bounded above by this number. Given \(n\) processors, we can apply any coloring in constant time, where every processor can compute the color of its element based on the hash function that is currently examined. This means that the coloring step in color coding takes \(FPP\)-time, so if other operations of a color coding algorithm can be efficiently parallelized, then the whole algorithm would run in \(FPP\)-time. The above result was used to prove multiple problems \(FPP\) in [17], especially graph packing problems such as parameterized Matching; \(k\)-Triangle Packing, which is nothing but finding \(k\) vertex-disjoint 3-cliques; and \((k,l)\)-Cycle Packing, which requires finding \(k\) vertex-disjoint cycles of length \(l\) each. In fact, it was shown that any problem that requires finding \(k\) vertex-disjoint copies of a graph \(H\) in an arbitrary graph \(G\) is in \(FPP\) as long as the order of \(H\) is constant or bounded by some parameter other than the order of \(G\). Formally, given an arbitrary graph \(G\) of order \(n\) and a \"fixed\" graph \(H\) of order \(h\), where \(h\) is a constant independent of \(n\). The question is whether \(G\) contains \(k\) disjoint subgraphs isomorphic to \(H\), where \(k\) is a parameter independent of \(n\). We shall describe how color coding is used (mainly in [17]) to obtain an \(FPP\) algorithm for the problem. First, determining whether a graph \(G_{1}\) of order \(n_{1}\) contains a subgraph isomorphic to \(H_{1}\) of constant-order \(h_{1}\) can be done in constant time using \(O(n_{1}^{h_{1}})\) processors, as there are at most that much subgraph of \(G_{1}\) that have order \(h_{1}\). Every processor checks in a constant time whether its subgraph is isomorphic to \(H_{1}\) (since \(h_{1}\) is a constant and querying the input as noted above is \(FPP\)). Now, to find at least \(k\) disjoint subgraphs isomorphic to \(H\) in \(G\), we will need color coding. Since the solution is of size \(k\), then exactly \(h*k\) vertices will be involved. In addition, if there is a solution, then an \((n,h*k,k)\) coloring family will contain at least one coloring where every subgraph of the \(k\) subgraphs in the solution is completely colored with a unique color. Generating the hash functions for the coloring and coloring the graph \(G\) with every possible coloring can be done in \(FPP\)-time, as mentioned above. For every coloring, and for every color of the \(k\) colors, check whether the subgraph of \(G\) induced by the vertices of this color (keep \(G\) as is, but only consider the vertices of one color) contains a subgraph isomorphic to \(H\). As shown previously, this takes \(FPP\)-time, so the overall algorithm becomes \(FPP\). The correctness of the algorithm follows from the fact that every coloring partitions \(G\) into \(k\) disjoint subgraphs. Hence, whenever a coloring function generates a valid solution, stop and return it; otherwise, continue to try all colorings, and report a NO instance if none gives a solution. Therefore, finding whether an arbitrary graph \(G\) contains at least \(k\) disjoint subgraphs isomorphic to some fixed, constant graph \(H\) is \(FPP\) and the algorithm described above runs in time \(O(log(k)*k^{(k*h)^{2}}*(k*h)^{4}*log^{2}(n))\) using \(O(n^{h})\) processors. A related problem that is amenable to the color coding method is (Induced) Subgraph Isomorphism. Consider an arbitrary graph \(G\) of order \(n\), and another arbitrary graph \(H\) of order \(k\) (where \(k\) is a parameter independent of \(n\)) along with a tree decomposition \((T,\tau)\) for \(H\).