Abstract
We investigate graph problems in the distributed sketching model, where each node sends a single message to a referee who computes the output. We define a class of graphs and give a framework for proving lower bounds for certain embeddable problems, which leads to several new results: First, we present a tight lower bound of Ω(n) bits for the message size of computing a breadthfirst search (BFS) tree. For locallycheckable labeling (LCL) problems, we show that verifying whether a given vertex labeling forms a weak 2coloring requires messages of Ω(n^{1/3}log^{2/3}n) bits, and the same lower bound holds for verifying whether a subset of nodes forms a maximal independent set. We also prove that computing a kedge connected spanning subgraph (kECSS) requires messages of size at least Ω(klog²(n/k)), which is tight up to a logarithmic factor. To show these results, we define a simultaneous multiparty (SMP) model of communication complexity, where the players obtain certain subgraphs as their input, and develop a generic embedding argument that allows us to prove lower bounds for the graph sketching model by using reductions from the SMP model. We point out that these results also extend to singleround algorithms in the broadcast congested clique.
We also (nearly) settle the space complexity of the kECSS problem in the streaming model by extending the work of Kapralov, Nelson, Pachoki, Wang, and Woodruff (FOCS 2017): We prove a communication complexity lower bound for a direct sum variant of the UR^⊂_k problem and show that this implies Ω(k nlog²(n/k)) bits of memory for computing a kECSS. This is known to be optimal up to a logarithmic factor.
BibTeX  Entry
@InProceedings{robinson:LIPIcs.DISC.2023.32,
author = {Robinson, Peter},
title = {{Distributed Sketching Lower Bounds for kEdge Connected Spanning Subgraphs, BFS Trees, and LCL Problems}},
booktitle = {37th International Symposium on Distributed Computing (DISC 2023)},
pages = {32:132:21},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959773010},
ISSN = {18688969},
year = {2023},
volume = {281},
editor = {Oshman, Rotem},
publisher = {Schloss Dagstuhl  LeibnizZentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2023/19158},
URN = {urn:nbn:de:0030drops191589},
doi = {10.4230/LIPIcs.DISC.2023.32},
annote = {Keywords: Distributed graph algorithm, graph sketching, streaming}
}
Keywords: 

Distributed graph algorithm, graph sketching, streaming 
Collection: 

37th International Symposium on Distributed Computing (DISC 2023) 
Issue Date: 

2023 
Date of publication: 

05.10.2023 