Journal of the Association for Computing Machinery, Vol. 42, No. 4, July 1995, pp. 844–856.

Color-coding

NOGA ALON

RAPHAEL YUSTER

AND

URI ZWICK

Abstract. We 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:

• 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^{ω}) expected time or O(V^{ω} log V) worst-case time, where ω < 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) worstcase 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).

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.

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

Copyright 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.