TR94-009 Authors: Noga Alon, Raphael Yuster, Uri Zwick

Publication: 12th December 1994 00:00

Downloads: 968

Keywords:

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.