<p>In the worst case, this algorithm gives a 2-approximation (the trivial upper bound).</p>
<p>Take a cycle on some <span class="math-container">$n=4m$</span> vertices, vertex set <span class="math-container">$v_0,\ldots,v_{n-1}$</span>, with one chord between <span class="math-container">$v_0$</span> and <span class="math-container">$v_{2m}$</span>. This graph has radius <span class="math-container">$m$</span> with centers <span class="math-container">$v_0$</span> and <span class="math-container">$v_{2m}$</span>. However, from vertex <span class="math-container">$v_m$</span> (or <span class="math-container">$v_{3m})$</span>, the longest shortest path has length <span class="math-container">$2m$</span>. 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.</p>

CC BY-SA 4.0
2022-04-11T10:53:41.250Z
2022-04-11T10:53:41.250Z
Highheath
<p>Given a graph <span class="math-container">$G=(V,E)$</span>, a center is a vertex <span class="math-container">$v\in V$</span> with minimal eccentricity (i.e., <span class="math-container">$v\in\text{argmin}_v\max_u d(u,v)$</span>).</p>
<p>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.</p>
<p>Namely, consider running BFS from an arbitrary node and getting a spanning tree <span class="math-container">$T$</span>. Then, we can compute the center <em>of the tree</em> in linear time.</p>
<p>I'm wondering how good this node would be as an approximation for the graph's true center.
That is:</p>
<blockquote>
<p><strong>What is the maximal possible ratio between the eccentricity of the <span class="math-container">$T$</span>'s center and that of <span class="math-container">$G$</span>'s center?</strong></p>
</blockquote>
<hr />
<p>Some initial thoughts about this:</p>
<ul>
<li><p>The ratio is trivially at most <span class="math-container">$2$</span> because <span class="math-container">$G$</span> is undirected.</p>
</li>
<li><p>The ratio could be <em>at least</em> <span class="math-container">$3/2-\epsilon$</span>. The reason is that the above can be implemented in <span class="math-container">$O(n)$</span> rounds distributedly in the CONGEST model, and there's <a href="https://arxiv.org/abs/1605.05109" rel="nofollow noreferrer">a known lower bound</a> for computing the radius with <span class="math-container">$\widetilde \Omega(n)$</span> rounds.</p>
</li>
</ul>

CC BY-SA 4.0
2022-04-06T13:14:12.143Z
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$.
Tassle
<graph-theory><graph-algorithms><lower-bounds><tree><upper-bounds>
Is the center of a BFS tree a good approximation of the graphs center?
Eli
# Is the center of a BFS tree a good approximation of the graphs center?

(Asked by: username_0 on 2022-04-06)

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](https://arxiv.org/abs/1605.05109) for computing the radius with $\widetilde \Omega(n)$ rounds.

**Tags:** graph-theory, graph-algorithms, lower-bounds, tree, upper-bounds

> **Comments:**
> **username_1**: 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$.  

---

## 1 answers

### Answer by username_2 on 2022-04-11. Score: 2

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.


---

