Complexity of distributively verifying that the diameter is small

Question

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, 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 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$?)

Answer 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.