Abstract
Graph spanners are sparse subgraphs which approximately preserve all pairwise shortestpath distances in an input graph. The notion of approximation can be additive, multiplicative, or both, and many variants of this problem have been extensively studied. We study the problem of computing a graph spanner when the edges of the input graph are distributed across two or more sites in an arbitrary, possibly worstcase partition, and the goal is for the sites to minimize the communication used to output a spanner. We assume the messagepassing model of communication, for which there is a pointtopoint link between all pairs of sites as well as a coordinator who is responsible for producing the output. We stress that the subset of edges that each site has is not related to the network topology, which is fixed to be pointtopoint. While this model has been extensively studied for related problems such as graph connectivity, it has not been systematically studied for graph spanners. We present the first tradeoffs for total communication versus the quality of the spanners computed, for two or more sites, as well as for additive and multiplicative notions of distortion. We show separations in the communication complexity when edges are allowed to occur on multiple sites, versus when each edge occurs on at most one site. We obtain nearly tight bounds (up to polylog factors) for the communication of additive 2spanners in both the with and without duplication models, multiplicative (2k1)spanners in the with duplication model, and multiplicative 3 and 5spanners in the without duplication model. Our lower bound for multiplicative 3spanners employs biregular bipartite graphs rather than the usual Erdős girth conjecture graphs and may be of wider interest.
BibTeX  Entry
@InProceedings{fernndezv_et_al:LIPIcs:2020:11762,
author = {Manuel Fern{\'a}ndez V and David P. Woodruff and Taisuke Yasuda},
title = {{Graph Spanners in the MessagePassing Model}},
booktitle = {11th Innovations in Theoretical Computer Science Conference (ITCS 2020)},
pages = {77:177:18},
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/11762},
URN = {urn:nbn:de:0030drops117620},
doi = {10.4230/LIPIcs.ITCS.2020.77},
annote = {Keywords: Graph spanners, Messagepassing model, Communication complexity}
}
Keywords: 

Graph spanners, Messagepassing model, Communication complexity 
Collection: 

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

2020 
Date of publication: 

06.01.2020 