AbstractWe describe a novel randomized method, the method of 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 perfect 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 graph G = (V,E) contains a simple cycle of size exactly k, then such a cycle can be found in either O(V^o) expected time or O(V^o log V) worst-case time, where o < 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.)
- For every fixed k, if a planar graph G = (V,E) contains a simple cycle of size 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 minor closed family of graphs which is not the family of all graphs.
- If a graph G = (V, E) contains a subgraph isomorphic to a 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 polynomial time. This was not previously known even if H were just a path of length O(log V).
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.