@online{Becker_arXIv1909.09002,
TITLE = {Low Diameter Graph Decompositions by Approximate Distance Computation},
AUTHOR = {Becker, Ruben and Emek, Yuval and Lenzen, Christoph},
LANGUAGE = {eng},
URL = {http://arxiv.org/abs/1909.09002},
EPRINT = {1909.09002},
EPRINTTYPE = {arXiv},
YEAR = {2019},
ABSTRACT = {In many models for large-scale computation, decomposition of the problem is<br>key to efficient algorithms. For distance-related graph problems, it is often<br>crucial that such a decomposition results in clusters of small diameter, while<br>the probability that an edge is cut by the decomposition scales linearly with<br>the length of the edge. There is a large body of literature on low diameter<br>graph decomposition with small edge cutting probabilities, with all existing<br>techniques heavily building on single source shortest paths (SSSP)<br>computations. Unfortunately, in many theoretical models for large-scale<br>computations, the SSSP task constitutes a complexity bottleneck. Therefore, it<br>is desirable to replace exact SSSP computations with approximate ones. However<br>this imposes a fundamental challenge since the existing constructions of such<br>decompositions inherently rely on the subtractive form of the triangle<br>inequality. The current paper overcomes this obstacle by developing a technique<br>termed blurry ball growing. By combining this technique with a clever<br>algorithmic idea of Miller et al. (SPAA 13), we obtain a construction of low<br>diameter decompositions with small edge cutting probabilities which replaces<br>exact SSSP computations by (a small number of) approximate ones. The utility of<br>our approach is showcased by deriving efficient algorithms that work in the<br>Congest, PRAM, and semi-streaming models of computation. As an application, we<br>obtain metric tree embedding algorithms in the vein of Bartal (FOCS 96) whose<br>computational complexities in these models are optimal up to polylogarithmic<br>factors. Our embeddings have the additional useful property that the tree can<br>be mapped back to the original graph such that each edge is "used" only O(log<br>n) times, which is of interest for capacitated problems and simulating Congest<br>algorithms on the tree into which the graph is embedded.<br>},
}