# Extended Longest Path problem

January 3, 2010 Leave a comment

These are slides from a talk on the Longest Path Problem at the Penn State Theory seminar.

In the Longest Path Problem, we are given an undirected graph, G =(V,E), and integer , and are asked to find out whether or not there exists a simple path of length k in G.

The Extended Longest Path Problem is a variant of the above. Here, we are asked to find out all pairs of vertices that have a simple path of length k between them.

The Longest Path problem is NP-complete.

The talk deals with 3 approaches to solving the Extended Longest Path Problem:-

1. Method of Random Orientations

2. Color-coding

3. Divide-and-color

All three methods use randomization.