Abstract:
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.