Color-coding

Abstract

We describe a novel randomized method.the method of cobm-coding for finding simple paths and cycles of a specified length k, and other small subgraphs, within a gwen graph G = ( 1', E).The randomized algorithms obtained using this method can be derandomlzcd using kmihes of petfect hash f~wtctmns.Using the color-coding method we obtain.m particular, the following new results:-For every fixed k, if a graph G = (V.E) contains a simple cycle of size exactly k, then such a cycle can be found m either 0( V'") expected time or 0( L'"' log P') worst-case t]mc, where w < ?,376 ]s the exponent of matrrx multiplication.(Here and in what follows we use V and E instead of Ib' and IEI whenever no confusion may arise.)-For every fwed k, if a planar graph G = (P-, E) contains a simple cycle of size e.wrctly k, then such a cycle cmr be found m either 0(V) expected time or 0( V log V ) worst-case time.The same algorithm applies, in fact, not only to planar gmphs, but to any mino~closed family of graphs which is not the f~mily of all graphs, -If a grdph G = (V, E) contains a subgraph isomorphic to a boanded tree-width graph H = ( V~, E~) where IV, I = O(log V), then such a copy of H can be found in polyzonzml tune.This was not prewously known even if H were Just a path of length O(log V).These results improve upon previous results of many authors.The third result resolves in the affirmative a conjecture of Papadimltnou and Yannakakis that the LOG PATH problem is m P. We can show that it is even in NC.