%%% ====================================================================
%%% @LaTeX-file{
%%% filename = "alonyz95.ltx",
%%% date = "16 May 1996",
%%% time = "15:06:26 EDT",
%%% author = "David M. Jones",
%%% email = "jacm@theory.lcs.mit.edu",
%%% url = "http://theory.lcs.mit.edu/~jacm/",
%%% address = "Journal of the ACM
%%% MIT Laboratory for Computer Science
%%% Room NE43-316
%%% 545 Technology Square
%%% Cambridge, MA 02139
%%% USA",
%%% telephone = "(617) 253-5936",
%%% FAX = "(617) 253-3480",
%%% checksum = "60856 105 565 4313",
%%% codetable = "ISO/ASCII",
%%% supported = "yes",
%%% docstring = "Copyright (c) 1995 by ACM, Inc.
%%% Permission to make digital or hard copies of part
%%% or all of this work for personal or classroom use
%%% is granted without fee provided that copies are
%%% not made or distributed for profit or direct
%%% commercial advantage and that copies bear this
%%% notice and the full citation on the first page.
%%% Copyrights for components of this work owned by
%%% others than ACM must be honored. Abstracting with
%%% credit is permitted. To copy otherwise, to
%%% republish, to post on servers, or to redistribute
%%% to lists, requires prior specific permission
%%% and/or a fee. Request permissions from
%%% Publications Dept, ACM Inc., fax +1 (212)
%%% 869-0481, or permissions@acm.org.
%%%
%%% This is a LaTeX2e file. To process it, you will
%%% need a copy of the acmabs document class, which is
%%% available via the following URL:
%%%
%%% http://theory.lcs.mit.edu/~jacm/acmart/acmabs.cls
%%% ",
%%% }
%%% ====================================================================
\documentclass{acmabs}
\begin{document}
\Journal{Journal of the ACM}
\refkey{AlonYZ95}
\title{Color-coding}
\author{Noga Alon \and Raphael Yuster \and Uri Zwick}
\Pages{844--856}
\Month{July}
\Year{1995}
\Volume{42}
\Number{4}
\maketitle
\begin{abstract}
We describe a novel randomized method, the method of \emph{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
\emph{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
\emph{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 \emph{planar} graph $G = (V,E)$ contains a
simple cycle of size \emph{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
algorithms applies, in fact, not only to planar graphs, but to any
\emph{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
\emph{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 \emph{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.
\end{abstract}
\begin{categories}
G.2.2 [\textbf{Discrete Mathematics}]: Graph Theory---\emph{graph
algorithms}; \emph{path and circuit problems}
\end{categories}
\end{document}