Is the center of a BFS tree a good approximation of the graphs center?

Question

Given a graph $G=(V,E)$, a center is a vertex $v\in V$ with minimal eccentricity (i.e., $v\in\text{argmin}_v\max_u d(u,v)$).

Finding the center of the graph can easily be done using all-pairs-shortest-paths, but I'm looking to approximate it with something that runs in linear time.

Namely, consider running BFS from an arbitrary node and getting a spanning tree $T$. Then, we can compute the center of the tree in linear time.

I'm wondering how good this node would be as an approximation for the graph's true center. That is:

What is the maximal possible ratio between the eccentricity of the $T$'s center and that of $G$'s center?

---

Some initial thoughts about this:

• The ratio is trivially at most $2$ because $G$ is undirected.

• The ratio could be at least $3/2-\epsilon$. The reason is that the above can be implemented in $O(n)$ rounds distributedly in the CONGEST model, and there's a known lower bound for computing the radius with $\widetilde \Omega(n)$ rounds.

Answer 1

In the worst case, this algorithm gives a 2-approximation (the trivial upper bound).

Take a cycle on some $n=4m$ vertices, vertex set $v_0,\ldots,v_{n-1}$, with one chord between $v_0$ and $v_{2m}$. This graph has radius $m$ with centers $v_0$ and $v_{2m}$. However, from vertex $v_m$ (or $v_{3m})$, the longest shortest path has length $2m$. Moreover, if you start a BFS from either of these two vertices, that vertex (or its neighbor) will be the center of the resulting tree.