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,