Near-Optimal Distributed Tree Embedding

Tree embeddings

are a powerful tool in the area of graph approximation algorithms. Essentially, they transform problems on general graphs into much easier ones on trees. Fakcharoenphol, Rao, and Talwar (FRT) [STOC’04] present a probabilistic tree embedding that transforms

n

-node metrics into (probability distributions over) trees, while

stretching

each pairwise distance by at most an

O

(log

n

) factor in expectation. This

O

(log

n

) stretch is optimal.

Khan et al. [PODC’08] present a distributed algorithm that implements FRT in

O

(SPD log

n

) rounds, where SPD is the

shortest-path-diameter

of the weighted graph, and they explain how to use this embedding for various distributed approximation problems. Note that SPD can be as large as Θ(

n

), even in graphs where the hop-diameter

D

is a constant. Khan et al. noted that it would be interesting to improve this complexity. We show that this is indeed possible.

More precisely, we present a distributed algorithm that constructs a tree embedding that is essentially as good as FRT in

$\tilde{O}(\min\{n^{0.5+\varepsilon },\operatorname{SPD}\}+D)$

rounds, for any constant

ε

 > 0. A lower bound of

$\tilde{\Omega}(\min\{n^{0.5},\operatorname{SPD}\}+D)$

rounds follows from Das Sarma et al. [STOC’11], rendering our round complexity near-optimal.