TY - GEN

T1 - Color-coding

T2 - 26th Annual ACM Symposium on Theory of Computing, STOC 1994

AU - Alon, Noga

AU - Yuster, Raphy

AU - Zwick, Uri

N1 - Funding Information:
*Work supported in part by The basic research foundation administrated by The Israel academy of sciences and humanities and by grant No. 93-6-6 of the Sloan foundation.
Publisher Copyright:
© 1994 ACM.

PY - 1994/5/23

Y1 - 1994/5/23

N2 - 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, among others, the following new results: l For every fixed k, if a graph G = (V, E) contains a simple cycle of size ezactly k, then such a cycle can be found in either O(VU) expected time or O (VW 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 IVI and IEI whenever no confusion may arise. ) l 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 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 lVHl = 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 t bird result resolves in the affirmative a conjecture of Papadimitriou and Yannakakis that the LOG PATH problem is in P. We can even show that the LOG PATH problem is in NC.

AB - 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, among others, the following new results: l For every fixed k, if a graph G = (V, E) contains a simple cycle of size ezactly k, then such a cycle can be found in either O(VU) expected time or O (VW 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 IVI and IEI whenever no confusion may arise. ) l 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 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 lVHl = 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 t bird result resolves in the affirmative a conjecture of Papadimitriou and Yannakakis that the LOG PATH problem is in P. We can even show that the LOG PATH problem is in NC.

UR - http://www.scopus.com/inward/record.url?scp=0028015158&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=0028015158&partnerID=8YFLogxK

U2 - 10.1145/195058.195179

DO - 10.1145/195058.195179

M3 - Conference contribution

AN - SCOPUS:0028015158

T3 - Proceedings of the Annual ACM Symposium on Theory of Computing

SP - 326

EP - 335

BT - Proceedings of the 26th Annual ACM Symposium on Theory of Computing, STOC 1994

PB - Association for Computing Machinery

Y2 - 23 May 1994 through 25 May 1994

ER -