Color-coding: A new method for finding simple paths, cycles and other small subgraphs within large graphs

Noga Mordechai Alon, Raphy Yuster, Uri Zwick

Research output: Chapter in Book/Report/Conference proceedingConference contribution

42 Scopus citations

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

Original languageEnglish (US)
Title of host publicationProceedings of the 26th Annual ACM Symposium on Theory of Computing, STOC 1994
PublisherAssociation for Computing Machinery
Pages326-335
Number of pages10
VolumePart F129502
ISBN (Electronic)0897916638
DOIs
StatePublished - May 23 1994
Externally publishedYes
Event26th Annual ACM Symposium on Theory of Computing, STOC 1994 - Montreal, Canada
Duration: May 23 1994May 25 1994

Other

Other26th Annual ACM Symposium on Theory of Computing, STOC 1994
CountryCanada
CityMontreal
Period5/23/945/25/94

All Science Journal Classification (ASJC) codes

  • Software

Fingerprint Dive into the research topics of 'Color-coding: A new method for finding simple paths, cycles and other small subgraphs within large graphs'. Together they form a unique fingerprint.

Cite this