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

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?

• 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.
• Take the graph $G=(V,E)$ with $V=\{1,2,3,4,5\}$ and $E=\{(1,2),(2,3),(3,4),(4,5), (1,4),(2,4)\}$. There is an execution of BFS starting at $3$ which yields the path going from $1$ to $5$ as a spanning tree. Its center is $3$ which has eccentricity $2$. The center of $G$ is $4$ and has eccentricity $1$. Apr 6, 2022 at 13:14
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.