Becker, Ruben ;
Emek, Yuval ;
Lenzen, Christoph
Low Diameter Graph Decompositions by Approximate Distance Computation
Abstract
In many models for largescale computation, decomposition of the problem is key to efficient algorithms. For distancerelated graph problems, it is often crucial that such a decomposition results in clusters of small diameter, while the probability that an edge is cut by the decomposition scales linearly with the length of the edge. There is a large body of literature on low diameter graph decomposition with small edge cutting probabilities, with all existing techniques heavily building on single source shortest paths (SSSP) computations. Unfortunately, in many theoretical models for largescale computations, the SSSP task constitutes a complexity bottleneck. Therefore, it is desirable to replace exact SSSP computations with approximate ones. However this imposes a fundamental challenge since the existing constructions of low diameter graph decomposition with small edge cutting probabilities inherently rely on the subtractive form of the triangle inequality, which fails to hold under distance approximation.
The current paper overcomes this obstacle by developing a technique termed blurry ball growing. By combining this technique with a clever algorithmic idea of Miller et al. (SPAA 2013), we obtain a construction of low diameter decompositions with small edge cutting probabilities which replaces exact SSSP computations by (a small number of) approximate ones. The utility of our approach is showcased by deriving efficient algorithms that work in the CONGEST, PRAM, and semistreaming models of computation. As an application, we obtain metric tree embedding algorithms in the vein of Bartal (FOCS 1996) whose computational complexities in these models are optimal up to polylogarithmic factors. Our embeddings have the additional useful property that the tree can be mapped back to the original graph such that each edge is "used" only logaritmically many times, which is of interest for capacitated problems and simulating CONGEST algorithms on the tree into which the graph is embedded.
BibTeX  Entry
@InProceedings{becker_et_al:LIPIcs:2020:11735,
author = {Ruben Becker and Yuval Emek and Christoph Lenzen},
title = {{Low Diameter Graph Decompositions by Approximate Distance Computation}},
booktitle = {11th Innovations in Theoretical Computer Science Conference (ITCS 2020)},
pages = {50:150:29},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959771344},
ISSN = {18688969},
year = {2020},
volume = {151},
editor = {Thomas Vidick},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2020/11735},
URN = {urn:nbn:de:0030drops117355},
doi = {10.4230/LIPIcs.ITCS.2020.50},
annote = {Keywords: graph decompositions, metric tree embeddings, distributed graph algorithms, parallel graph algorithms, (semi)streaming graph algorithms}
}
2020
Keywords: 

graph decompositions, metric tree embeddings, distributed graph algorithms, parallel graph algorithms, (semi)streaming graph algorithms 
Seminar: 

11th Innovations in Theoretical Computer Science Conference (ITCS 2020)

Issue date: 

2020 
Date of publication: 

2020 