For every fixed constant, and every graph that is in any nontrivial minor-closed graph family, if contains a simple cycle of size, then such cycle can be found in:
* expected time, or
* worst-case time.
If a graph contains a subgraph isomorphic to a bounded treewidth graph which has vertices, then such a subgraph can be found in polynomial time.
The method
To solve the problem of finding a subgraph in a given graph, where can be a path, a cycle, or any bounded treewidth graph where, the method of color-coding begins by randomly coloring each vertex of with colors, and then tries to find a colorful copy of in colored. Here, a graph is colorful if every vertex in it is colored with a distinct color. This method works by repeating random coloring a graph and finding colorful copy of the target subgraph, and eventually the target subgraph can be found if the process is repeated a sufficient number of times. Suppose a copy of in becomes colorful with some non-zero probability. It immediately follows that if the random coloring is repeated times, then this copy is expected to become colorful once. Note that though is small, it is shown that if, is only polynomially small. Suppose again there exists an algorithm such that, given a graph and a coloring which maps each vertex of to one of the colors, it finds a copy of colorful, if one exists, within some runtime. Then the expected time to find a copy of in, if one exists, is. Sometimes it is also desirable to use a more restricted version of colorfulness. For example, in the context of finding cycles in planar graphs, it is possible to develop an algorithm that finds well-colored cycles. Here, a cycle is well-colored if its vertices are colored by consecutive colors.
Example
An example would be finding a simple cycle of length in graph. By applying random coloring method, each simple cycle has a probability of to become colorful, since there are ways of coloring the vertices on the cycle, among which there are colorful occurrences. Then an algorithm can be used to find colorful cycles in the randomly colored graphin time, where is the matrixmultiplication constant. Therefore, it takes overall time to find a simple cycle of length in. The colorful cycle-finding algorithm works by first finding all pairs of vertices in that are connected by a simple path of length, and then checking whether the two vertices in each pair are connected. Given a coloring function to color graph, enumerate all partitions of the color set into two subsets of size each. Note that can be divided into and accordingly, and let and denote the subgraphs induced by and respectively. Then, recursively find colorful paths of length in each of and. Suppose the boolean matrix and represent the connectivity of each pair of vertices in and by a colorful path, respectively, and let be the matrix describing the adjacency relations between vertices of and those of, the boolean product gives all pairs of vertices in that are connected by a colorful path of length. Thus, the recursive relation of matrix multiplications is, which yields a runtime of. Although this algorithm finds only the end points of the colorful path, another algorithm by Alon and Naor that finds colorful paths themselves can be incorporated into it.
Derandomization
The derandomization of color-coding involves enumerating possible colorings of a graph, such that the randomness of coloring is no longer required. For the target subgraph in to be discoverable, the enumeration has to include at least one instance where the is colorful. To achieve this, enumerating a -perfect family of hash functions from to is sufficient. By definition, is -perfect if for every subset of where, there exists a hash function in such that is perfect. In other words, there must exist a hash function in that colors any given vertices with distinct colors. There are several approaches to construct such a -perfect hash family:
The best explicit construction is by Moni Naor, Leonard J. Schulman, and Aravind Srinivasan, where a family of size can be obtained. This construction does not require the target subgraph to exist in the original subgraph finding problem.
Another explicit construction by Jeanette P. Schmidt and Alan Siegel yields a family of size.
Another construction that appears in the original paper of Noga Alon et al. can be obtained by first building a -perfect family that maps to followed by building another -perfect family that maps to In the first step, it is possible to construct such a family with random bits that are almost -wise independent, and the sample space needed for generating those random bits can be as small as. In the second step, it has been shown by Jeanette P. Schmidt and Alan Siegel that the size of such -perfect family can be. Consequently, by composing the -perfect families from both steps, a -perfect family of size that maps from to can be obtained.
In the case of derandomizing well-coloring, where each vertex on the subgraph is colored consecutively, a -perfect family of hash functions from to is needed. A sufficient -perfect family which maps from to can be constructed in a way similar to the approach 3 above. In particular, it is done by using random bits that are almost independent, and the size of the resulting -perfect family will be. The derandomization of color-coding method can be easily parallelized, yielding efficient NC algorithms.
Applications
Recently, color-coding has attracted much attention in the field of bioinformatics. One example is the detection of signaling pathways in protein-protein interaction networks. Another example is to discover and to count the number of motifs in PPI networks. Studying both signaling pathways and motifs allows a deeper understanding of the similarities and differences of many biological functions, processes, and structures among organisms. Due to the huge amount of gene data that can be collected, searching for pathways or motifs can be highly time consuming. However, by exploiting the color-coding method, the motifs or signaling pathways with vertices in a network with vertices can be found very efficiently in polynomial time. Thus, this enables us to explore more complex or larger structures in PPI networks.
