The following technical report is available from http://aib.informatik.rwth-aachen.de:
Divide-and-Color Joachim Kneis, Daniel Mölle, Stefan Richter, Peter Rossmanith AIB 2006-06
We introduce divide-and-color, a new technique for the solution of hard graph problems. It is a combination of the well-known divide-and-conquer paradigm and color-coding. Our approach first randomly colors all edges or nodes of a graph black and white, and then solves the problem recursively on the two induced parts.
We demonstrate this technique by giving new randomized algorithms for the solution of two important problems. These yield runtime bounds of O*(4^k) for finding a simple path of length k and O*(4^((h-1)k)) for finding k edge-disjoint (resp. vertex-disjoint) copies of a graph H with h edges (resp. h nodes) in a given graph. Derandomization gives deterministic algorithms for these problems with running times O*(2^(4k))$ and O*(2^(4hk))$, respectively.
All these results significantly improve over the currently known best bounds. In particular, our generic algorithms beat specialized ones that have been designed to find k triangles or paths of length two.