3
$\begingroup$

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

$\endgroup$
1
$\begingroup$

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.

$\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.