2
$\begingroup$

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.

$\endgroup$
1
  • 1
    $\begingroup$ 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$. $\endgroup$
    – Tassle
    Apr 6 at 13:14

1 Answer 1

2
$\begingroup$

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.

$\endgroup$

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.