Optimal lower bounds for distributed and streaming spanning forest computation

DOI10.1137/1.9781611975482.111MaRDI QIDQ5236295zbMATH OpenOpenAlexFDO

Authors Jelani Nelson, Huacheng Yu

Publication date 15 October 2019

Published in Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1807.05135

Mathematics Subject Classification ID

Data structures (68P05) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph theory (including graph drawing) in computer science (68R10)

Abstract: We show optimal lower bounds for spanning forest computation in two different models: * One wants a data structure for fully dynamic spanning forest in which updates can insert or delete edges amongst a base set of $n$ vertices. The sole allowed query asks for a spanning forest, which the data structure should successfully answer with some given (potentially small) constant probability $epsilon>0$. We prove that any such data structure must use $Omega(nlo{g}^{3}n)$ bits of memory. * There is a referee and $n$ vertices in a network sharing public randomness, and each vertex knows only its neighborhood; the referee receives no input. The vertices each send a message to the referee who then computes a spanning forest of the graph with constant probability $epsilon>0$. We prove the average message length must be $Omega(lo{g}^{3}n)$ bits. Both our lower bounds are optimal, with matching upper bounds provided by the AGM sketch [AGM12] (which even succeeds with probability $1-1/mathrmpoly(n)$). Furthermore, for the first setting we show optimal lower bounds even for low failure probability $delta$, as long as $delta>2^{-n^{1-epsilon}}$.

Recommendations

• Faster Fully-Dynamic Minimum Spanning Forest
• Broadcasting spanning forests on a multiple-access channel
• Dynamic graph stream algorithms in \(o(n)\) space
• Constant-time dynamic weight approximation for minimum spanning forest
• Dynamic graph stream algorithms in \(o(n)\) space

Cited in

(7)

• Randomized Lower Bound for Distributed Spanning-Tree Verification
• Fully dynamic connectivity in \(O(\log n(\log\log n)^2)\) amortized expected time
• Connectivity lower bounds in broadcast congested clique
• Streaming algorithms for connectivity augmentation
• Rounds vs. communication tradeoffs for maximal independent sets
• Streaming graph algorithms in the massively parallel computation model
• Learning spanning forests optimally in weighted undirected graphs with CUT queries

This page was built for publication: Optimal lower bounds for distributed and streaming spanning forest computation

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5236295)