Color-coding

In computer science and graph theory, the method of color-coding[1][2] efficiently finds k-vertex simple paths, k-vertex cycles, and other small subgraphs within a given graph using probabilistic algorithms, which can then be derandomized and turned into deterministic algorithms. This method shows that many subcases of the subgraph isomorphism problem (an NP-complete problem) can in fact be solved in polynomial time.

An example would be finding a simple cycle of length k in graph G = (V,E).

By applying random coloring method, each simple cycle has a probability of k!/k^k > \tfrac{1}{e^k} to become colorful, since there are kk ways of coloring the k vertices on the path, among which there are k! colorful occurrences.