<p>There is an $O(k)$ rounds algorithm for distinguishing between graphs of diameter at most $k$ and those with a diameter larger than $2k$.</p>

<p>This works in two stages:</p>

<p>First, each vertex broadcasts the smallest ID it has learned about for $k/2$ rounds.
For a vertex $v$, let $L_v$ be the smallest ID that $v$ has observed by the end of this stage.</p>

<p>Next, the algorithm makes $k+1$, such that in each iteration every vertex broadcasts the largest $L_v$ and smallest $L_u$ it has learned about. If the graph is indeed of diameter $k$, then we would have these equal in all vertices.</p>

<p>Assume that the graph has a diameter larger than $2k$, then any vertex $v$ has a path of length at least $k+1$ starting from it. This means that there exists a vertex $u$ such that $d(u,v)=k+1&gt; 2(k/2)$ which implies $L_u\neq L_v$. Thus, both $u,v$ would learn that not all vertices agreed on the node with the minimal identifier. </p>

CC BY-SA 4.0
2018-06-20T18:06:39.903Z
2018-06-20T18:06:39.903Z
R B
<p>Consider a graph $G=(V,E)$ and an integer parameter $k$.</p>

<p>I'm interested in the round complexity, in the CONGEST model, of checking if the diameter of the graph is "much larger" or "much smaller" than $k$.</p>

<p>Formally, assume that we need (all vertices) to report "small" if the diameter is at most $k$ and "large" if it is larger than $f(k)$ for some function $f$ (e.g., $f(k)=100k^2$).</p>

<p>A closely related problem asks to approximate the diameter. In this <a href="https://arxiv.org/pdf/1705.02127.pdf" rel="nofollow noreferrer">paper</a>, it was shown that deciding whether the diameter is at most $2\ell+1$ or larger than  $3\ell+1$ requires $\widetilde \Omega(n)$ rounds for any $1\le \ell\le \text{polylog}(n)$. However, this just shows that a (small) constant factor approximation is hard. </p>

<p>On the algorithmic front, <a href="https://pdfs.semanticscholar.org/92f7/46068b9a3718dbce64ec370b204ffc8ad13f.pdf" rel="nofollow noreferrer">it is possible</a> to compute a $3/2$-approximation in $O(\sqrt{n\log n}+D)$ rounds.</p>

<blockquote>
  <p>Does the round complexity depends on $n$ for <em>any</em> function $f(k)$? Are there functions $f$ for which this dependency is reduced, say, to logarithmic?</p>
</blockquote>

<hr>

<blockquote>
  <p>If we allow super-linear functions $f$, is it possible to reduce the dependency on the diameter (e.g., to $f^{-1}(D)$)? (e.g., can we get a round complexity of $O(k^2 \sqrt{n})$ for $f(k)=k^2$?)</p>
</blockquote>

<cc.complexity-theory><ds.algorithms><graph-algorithms><approximation-algorithms><dc.distributed-comp>
Complexity of distributively verifying that the diameter is small
R B
# Complexity of distributively verifying that the diameter is small

(Asked by: username_0 on 2018-06-13)

Consider a graph $G=(V,E)$ and an integer parameter $k$.

I'm interested in the round complexity, in the CONGEST model, of checking if the diameter of the graph is "much larger" or "much smaller" than $k$.

Formally, assume that we need (all vertices) to report "small" if the diameter is at most $k$ and "large" if it is larger than $f(k)$ for some function $f$ (e.g., $f(k)=100k^2$).

A closely related problem asks to approximate the diameter. In this [paper](https://arxiv.org/pdf/1705.02127.pdf), it was shown that deciding whether the diameter is at most $2\ell+1$ or larger than $3\ell+1$ requires $\widetilde \Omega(n)$ rounds for any $1\le \ell\le \text{polylog}(n)$. However, this just shows that a (small) constant factor approximation is hard.

On the algorithmic front, [it is possible](https://pdfs.semanticscholar.org/92f7/46068b9a3718dbce64ec370b204ffc8ad13f.pdf) to compute a $3/2$-approximation in $O(\sqrt{n\log n}+D)$ rounds.

> Does the round complexity depends on $n$ for *any* function $f(k)$? Are there functions $f$ for which this dependency is reduced, say, to logarithmic?

---

> If we allow super-linear functions $f$, is it possible to reduce the dependency on the diameter (e.g., to $f^{-1}(D)$)? (e.g., can we get a round complexity of $O(k^2 \sqrt{n})$ for $f(k)=k^2$?)

**Tags:** cc.complexity-theory, ds.algorithms, graph-algorithms, approximation-algorithms, dc.distributed-comp


---

## 1 answers

### Answer by username_0 on 2018-06-20. Score: 1

There is an $O(k)$ rounds algorithm for distinguishing between graphs of diameter at most $k$ and those with a diameter larger than $2k$.

This works in two stages:

First, each vertex broadcasts the smallest ID it has learned about for $k/2$ rounds.
For a vertex $v$, let $L\_v$ be the smallest ID that $v$ has observed by the end of this stage.

Next, the algorithm makes $k+1$, such that in each iteration every vertex broadcasts the largest $L\_v$ and smallest $L\_u$ it has learned about. If the graph is indeed of diameter $k$, then we would have these equal in all vertices.

Assume that the graph has a diameter larger than $2k$, then any vertex $v$ has a path of length at least $k+1$ starting from it. This means that there exists a vertex $u$ such that $d(u,v)=k+1> 2(k/2)$ which implies $L\_u\neq L\_v$. Thus, both $u,v$ would learn that not all vertices agreed on the node with the minimal identifier.


---

