AbstractWe describe a novel randomized method, the method of

color-codingfor finding simple paths and cycles of a specified lengthk, and other small subgraphs, within a given graphG= (V,E). The randomized algorithms obtained using this method can be derandomized using families ofperfect hash functions. Using the color-coding method we obtain, in particular, the following new results: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. Copyright 1995 by ACM, Inc.

- For every fixed
k, if a graphG= (V,E) contains a simple cycle of sizeexactlyk, then such a cycle can be found in eitherO(V^o) expected time orO(V^o logV) worst-case time, whereo< 2.376 is the exponent of matrix multiplication. (Here and in what follows we useVandEinstead of |V| and |E| whenever no confusion may arise.)- For every fixed
k, if aplanar graphG= (V,E) contains a simple cycle of sizeexactlyk, then such a cycle can be found in eitherO(V) expected time orO(VlogV) worst-case time. The same algorithms applies, in fact, not only to planar graphs, but to anyminor closed familyof graphs which is not the family of all graphs.- If a graph
G= (V,E) contains a subgraph isomorphic to abounded tree-widthgraphH= (V_H,E_H) where |V_H| =O(logV), then such a copy ofHcan be found inpolynomial time. This was not previously known even ifHwere just a path of lengthO(logV).The abstract is also available as a LaTeX file, a DVI file, or a PostScript file.

Preliminary versionA preliminary version of these results was presented in: Noga Alon, Raphy Yuster, and Uri Zwick. Color-coding: a new method for finding simple paths, cycles and other small subgraphs within large graphs (extended abstract). In Proceedings of the Twenty-Sixth Annual ACM Symposium on the Theory of Computing, pages 326-335, Montréal, Québec, Canada, 23-25 May 1994.

Categories and Subject Descriptors: G.2.2 [Discrete Mathematics]: Graph Theory --graph algorithms,path and circuit problems

Selected papers that cite this one

- N. Alon, R. Yuster, and U. Zwick. Finding and counting given length cycles. Algorithmica, 17(3):209-223, March 1997.

Selected references

- David Eppstein. Subgraph isomorphism in planar graphs and related problems. In Proceedings of the Sixth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 632-640, San Francisco, California, 22-24 January 1995.

- Michael L. Fredman, János Komlós, and Endre Szemerédi. Storing a sparse table with
O(1) worst case access time. Journal of the ACM, 31(3):538-544, July 1984.

- Martin Fürer and Balaji Raghavachari. Approximating the minimum degree spanning tree to within one from the optimal degree. In Proceedings of the Third Annual ACM-SIAM Symposium on Discrete Algorithms, pages 317-324, Orlando, Florida, 27-29 January 1992.

- David W. Matula and Leland L. Beck. Smallest-last ordering and clustering and graph coloring algorithms. Journal of the ACM, 30(3):417-427, July 1983.

- Joseph Naor and Moni Naor. Small-bias probability spaces: Efficient constructions and applications. In Proceedings of the Twenty Second Annual ACM Symposium on Theory of Computing, pages 213-223, Baltimore, Maryland, 14-16 May 1990.