3
$\begingroup$

A diametral path in a graph is a shortest path whose length is equal to the diameter of the graph. Now, given a tree with $n$ nodes, I would like to find the set of edges (possibly empty) which are present in all diametral paths. Is there an efficient algorithm to do that?

I know how to do it in $O(n^3)$ which is basically to iterate over all pairs of leaf nodes, check if their distance is equal to the diameter (this can be done using LCA) and if it is then traverse the (unique) path connecting them adding 1 to a counter associated to each edge along the way, and finally count how many edges have their counters equal to the number of diameters. This should work but it's quite expensive, and for sure there must be a more efficient approach.

$\endgroup$
0
$\begingroup$

An $O(n^2)$ algorithm is, for each edge, remove the edge and check the diameter of the tree (the forest now). If it did not change, then the edge is not in the set.

Finding the diameter of a tree can be done in linear time See here.

However, you can apply a greedy/dp trick for an $O(n)$ algorithm. First, root the tree at some vertex $r$. Hence, each vertex, except for $r$ gets a parent. You can then from the leaves up, find the distance from a vertex to the farthest leaf in its sub-tree. Actually, we will also keep the value of the longest path when the child having the current longest path is removed. After we compute all these values in a bottom-up manner, we go again top-down, computing for each vertex, the longest path from this vertex to a leaf not in its sub-tree. Now we can on $O(deg(v))$ compute for all edges incident to $v$ if there is a path of length equal to the maximum length and not using them.

The sum of the degrees is twice as large as the number of edges in The graph hence we get a linear total running time.

$\endgroup$
  • 1
    $\begingroup$ Wow right, that's one order more efficient. However I'm afraid that's not fast enough yet. I'm trying to solve this problem $\endgroup$ – Pablo Messina Sep 11 at 1:26
  • $\begingroup$ It seems linear-time solvable, but that was my first thought $\endgroup$ – narek Bojikian Sep 11 at 5:29
  • $\begingroup$ try with a bottom-up dp.. it should be something like that $\endgroup$ – narek Bojikian Sep 11 at 5:31
  • $\begingroup$ updated.. think of the specifications yourself. I will be glad to clarify any ambiguities $\endgroup$ – narek Bojikian Sep 11 at 5:43

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.