## 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 language | English (US) |
---|---|

Title of host publication | Proceedings of the 26th Annual ACM Symposium on Theory of Computing, STOC 1994 |

Publisher | Association for Computing Machinery |

Pages | 326-335 |

Number of pages | 10 |

Volume | Part F129502 |

ISBN (Electronic) | 0897916638 |

DOIs | |

State | Published - May 23 1994 |

Externally published | Yes |

Event | 26th Annual ACM Symposium on Theory of Computing, STOC 1994 - Montreal, Canada Duration: May 23 1994 → May 25 1994 |

### Other

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

Country | Canada |

City | Montreal |

Period | 5/23/94 → 5/25/94 |

## All Science Journal Classification (ASJC) codes

- Software