We describe a novel randomized method, the method of color-coding for
finding simple paths and cycles of a specified length k. and other sma
ll subgraphs, within a given graph G = (V, E). The randomized algorith
ms obtained using this method can be derandomized using families of pe
rfect hash functions. Using the color-coding method we obtain, in part
icular, the following new results: For every fixed k, if a graph G = (
V, E) contains a simple cycle of size exactly k, then such a cycle can
be found in either O(V-omega) expected time or O(V-omega log V) worst
-case time, where omega < 2.376 is the exponent of matrix multiplicati
on. (Here and in what follows we use V and E instead of \V\ and \E\ wh
enever no confusion may arise.) For every fixed k, if a planar graph G
= (V, E) contains a simple cycle of size exactly k, then such a cycle
can be found in either O(V) expected time or O(V log V) worst-case ti
me. The same algorithm applies, in fact, not only to planar graphs, bu
t to any minor closed family of graphs which is not the family of all
graphs. If a graph G = (V, E) contains a subgraph isomorphic to a boun
ded tree-width graph H = (V-H, E(H)) where \V-H\ = O(log V), then such
a copy of H can be found in polynomial time. This was not previously
known even if H were just a path of length O(log V). These results imp
rove upon previous results of many authors. The third result resolves
in the affirmative a conjecture of Papadimitriou and Yannakakis that t
he LOG PATH problem is in P. We can show that it is even in NC.