We describe a novel randomized method, the method of
{\em color-coding\/} for finding simple paths and cycles of a specified
length $k$, and other small subgraphs, within a given graph $G=(V,E)$.
The randomized algorithms obtained using this method can be
derandomized using families of {\em perfect hash functions\/}. Using
the color-coding method we obtain, in particular, the following new
results:

\begin{itemize}

\item For every fixed~$k$, if a graph $G=(V,E)$ contains a simple
cycle of size {\em 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 multiplication. (Here and in what
follows we use $V$ and~$E$ instead of $|V|$ and $|E|$ whenever no confusion
may arise.)

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

\item If a graph $G=(V,E)$ contains a subgraph isomorphic to a
{\em bounded tree-width\/} graph $H=(V_H,E_H)$ where $|V_H|=O(\log V)$, 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(\log V)$.

\end{itemize}

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