How to find longest path in graph?

Question

We are given an Adjacency list of the form

U -> (U,V,C) -> (U,V,C) ...  
U2 -> ...  
U3 -> ...  
.  
.  
etc

(U,V,C) means there's an edge from U to V with cost C.

The given Adjacency list is for a single connected tree with N nodes thus containing N-1 edges.

A set of nodes F=F1,F2,F3...Fk are given.

Now the question is what is the best way to find the longest path amongst the nodes in F? Is it possible to do it in O(N)?

Is DFS from each node in F the only option?

Answer 1

I understood your question as asking to find a pair of nodes from the set F so that the unique path between those two nodes is as long as it can be. The path is unique because your graph is a tree.

The problem can be solved trivially by doing DFS from every node in F as you mention, for an O(n k) solution where n is the size of the graph and k is the size of the set F.

However, you can solve it potentially faster by a divide and conquer approach. Pick any node R from the graph, and use a single DFS to tabulate distances Dist(R, a) to every other node a a and at the same time partition the nodes to subtrees S1,...,Sm where m is the number of edges from R; that is, these are the m trees hanging at the root R. Now, for any f and g that belong to different subtrees it holds that the path between them has Dist(R, f) + Dist(R, g) edges, so it is possible to search for the longest such path in O(k^2) time. In addition, you have then to recurse to the subproblems S1,...,Sm to cover the case where the longest path is inside one of those trees. The overall complexity can be lower than O(n k) but the math is left as an exercise to the reader.