Approximation algorithem for finding diameter of a graph

Question

Given Graph G=(V,E) ,undirected and weightless, we would want to find the value of diameter D of graph G. Show how to find a value X such that X<=D<=2*X in running time of O(|V|+|E|).

Now, to find the actual diameter of graph you simply need to run BFS twice.Once from and arbitrary node and then from the most distend node. But in this question I need to find an approximation to the diameter. My guess was to run BFS once and choosing the largest distance as the diameter. There are two edge cases that can occur.

The first one occur when the chosen node is located on the perimeter of graph G. The distend node will be located on the opposite side of the perimeter and thus X will be equal to D.

The second case will occur when the chosen node is in the center of G and X will be equal to half of D( X in this case will be the radios of G).

This was my answer to this question. And yet I was given 15/25 . Is there an edge case that I didn't handle or was it wrong from the start?

Thank you in advance.

Answer 1

60% seems a bit harsh to this former algorithms TA -- you gave the correct algorithm and identified the extremal cases for the two inequalities. Nevertheless, I agree with amit that you needed to give a formal proof. If your graders are particularly strict, you might have needed to say a word or two as well about why your algorithm is linear-time.

Here's the start of a formal proof. Let d(v, w) be the minimum length of a path between vertices v and w. The diameter is defined to be D = max_{v, w} d(v, w). Your algorithm chooses an arbitrary vertex s and outputs X = max_{w} d(s, w).

You need to do a little bit of algebra to show two facts: that X <= D and that D <= 2 X. You'll need the triangle inequality d(a, b) + d(b, c) >= d(a, c), which holds for all vertices a, b, c, as well as the symmetry d(a, b) = d(b, a).