License: Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.DISC.2023.32
URN: urn:nbn:de:0030-drops-191589
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2023/19158/
Go to the corresponding LIPIcs Volume Portal

Robinson, Peter

Distributed Sketching Lower Bounds for k-Edge Connected Spanning Subgraphs, BFS Trees, and LCL Problems

pdf-format:
LIPIcs-DISC-2023-32.pdf (1 MB)

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 breadth-first search (BFS) tree. For locally-checkable labeling (LCL) problems, we show that verifying whether a given vertex labeling forms a weak 2-coloring 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 k-edge connected spanning subgraph (k-ECSS) 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 single-round algorithms in the broadcast congested clique.
We also (nearly) settle the space complexity of the k-ECSS 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 k-ECSS. 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 k-Edge Connected Spanning Subgraphs, BFS Trees, and LCL Problems}},
  booktitle =	{37th International Symposium on Distributed Computing (DISC 2023)},
  pages =	{32:1--32:21},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-301-0},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{281},
  editor =	{Oshman, Rotem},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2023/19158},
  URN =		{urn:nbn:de:0030-drops-191589},
  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

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI