Color-coding

In computer science and graph theory, the term color-coding refers to an algorithmic technique which is useful in the discovery of network motifs. For example, it can be used to detect a simple path of length k in a given graph. The traditional color-coding algorithm is probabilistic, but it can be derandomized without much overhead in the running time. Color-coding also applies to the detection of cycles of a given length, and more generally it applies to the subgraph isomorphism problem (an NP-complete problem), where it yields polynomial time algorithms when the subgraph pattern that it is trying to detect has bounded treewidth. The color-coding method was proposed and analyzed in 1994 by Noga Alon, Raphael Yuster, and Uri Zwick. The following results can be obtained through the method of color-coding: For every fixed constant k, if a graph G = (V, E) contains a simple cycle of size k, then such a cycle can be found in: expected time, or worst-case time, where ω is the exponent of matrix multiplication. For every fixed constant k, and every graph G = (V, E) that is in any nontrivial minor-closed graph family (e.g., a planar graph), if G contains a simple cycle of size k, then such cycle can be found in: O(V) expected time, or O(V log V) worst-case time. If a graph G = (V, E) contains a subgraph isomorphic to a bounded treewidth graph which has O(log V) vertices, then such a subgraph can be found in polynomial time. To solve the problem of finding a subgraph in a given graph G = (V, E), where H can be a path, a cycle, or any bounded treewidth graph where , the method of color-coding begins by randomly coloring each vertex of G with colors, and then tries to find a colorful copy of H in colored G. Here, a graph is colorful if every vertex in it is colored with a distinct color. This method works by repeating (1) random coloring a graph and (2) 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.