5
$\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.

Improve this question
$\endgroup$
0

1 Answer 1

Reset to default
1
$\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.

Improve this answer
$\endgroup$
5
  • 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
    Commented Sep 11, 2019 at 1:26
  • $\begingroup$ It seems linear-time solvable, but that was my first thought $\endgroup$
    – Narek Bojikian
    Commented Sep 11, 2019 at 5:29
  • $\begingroup$ try with a bottom-up dp.. it should be something like that $\endgroup$
    – Narek Bojikian
    Commented Sep 11, 2019 at 5:31
  • $\begingroup$ updated.. think of the specifications yourself. I will be glad to clarify any ambiguities $\endgroup$
    – Narek Bojikian
    Commented Sep 11, 2019 at 5:43
  • $\begingroup$ Some good ideas here but I don't think your $O(n)$ approach solves it: Whether or not an edge (that is on some geodesic path) should be in the solution can depend on edges arbitrarily far away, but it looks like you are using just a "local" test. E.g. for a tree that is a "star of paths" (say, 3 paths of 10 vertices each, which all share a vertex at one end, namely the "centre"), the solution is the empty set, since for any edge $uv$, the pair of leaves on the other two paths define a geodesic path. But just checking paths through $u$ and/or $v$ is not enough to tell you this. $\endgroup$
    – j_random_hacker
    Commented Jun 7, 2020 at 13:03

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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