We describe a novel randomized method, the method of {\em color-coding\/} for finding simple paths and cycles of a specifiedlength k, and other small subgraphs, within a given graph G=(VE) .The randomized algorithms obtained using this method can bederandomized using families of {\em perfect hash functions\/}. Usingthe color-coding method we obtain, in particular, the following newresults:

\begin{itemize}

\item For every fixed~k, if a graph G=(VE) contains a simple cycle of size {\em exactly\/} k, then such a cycle can be found in eitherO(V) expected time or O(VlogV) worst-case time, where 2376 is the exponent of matrix multiplication. (Here and in whatfollows we use V and~E instead of V and E whenever no confusionmay arise.)

\item For every fixed~k, if a {\em planar\/} graph G=(VE) contains a simple cycle of size {\em exactly\/} k, then such a cycle can be found in either O(V) expected time or O(VlogV) worst-case time. The samealgorithm applies, in fact, not only to planar graphs, but to any {\emminor closed\/} family of graphs which is not the family of all graphs.

\item If a graph G=(VE) contains a subgraph isomorphic to a {\em bounded tree-width\/} graph H=(VHEH) where VH=O(logV) , then such a copy of H can be found in {\em polynomial time\/}. This was not previously known even if H were just a path of length O(logV).

\end{itemize}

These results improve upon previous results of many authors.The third result resolves in the affirmative a conjecture of Papadimitriouand Yannakakis that the LOG PATH problem is in P. We can show that it iseven in NC.