We describe a novel randomized method, the method of color-coding for nding simple paths and cycles of a specied 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 xed 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 ! logV ) worst-case time, where ! < 2:376 is the exponent of matrix multiplication. (Here and in what follows we use V and E instead ofjVj andjEj whenever no confusion may arise.) For every xed 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 logV ) worst-case time. The same algorithm 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 = (VH;EH) where jVHj = O(logV ), 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(logV ). These results improve upon previous results of many authors. The third result resolves in the armative a conjecture of Papadimitriou and Yannakakis that the LOG PATH problem is in P. We can show that it is even in NC.

Let A and B two n × n matrices over a ring R (e.g., the reals or the integers) each containing at most m nonzero elements. We present a new algorithm that multiplies A and B using O ( m ^0.7 n ^1.2 + n ^{2+ o (1)} ) algebraic operations (i.e., multiplications, additions and subtractions) over R . The naïve matrix multiplication algorithm, on the other hand, may need to perform Ω( mn ) operations to accomplish the same task. For m ≤ n ^1.14 , the new algorithm performs an almost optimal number of only n ^{2+ o (1)} operations. For m ≤ n ^1.68 , the new algorithm is also faster than the best known matrix multiplication algorithm for dense matrices which uses O ( n ^2.38 ) algebraic operations. The new algorithm is obtained using a surprisingly straightforward combination of a simple combinatorial idea and existing fast rectangular matrix multiplication algorithms. We also obtain improved algorithms for the multiplication of more than two sparse matrices. As the known fast rectangular matrix multiplication algorithms are far from being practical, our result, at least for now, is only of theoretical value.