Robust Lower Bounds for Graph Problems in the Blackboard Model of Communication

Konrad, Christian, Robinson, Peter and Zamaraev, Viktor ORCID: 0000-0001-5755-4141
(2021) Robust Lower Bounds for Graph Problems in the Blackboard Model of Communication. [Preprint]

[img] Text
2103.07027v1.pdf - Submitted version

Download (254kB) | Preview


We give lower bounds on the communication complexity of graph problems in the multi-party blackboard model. In this model, the edges of an $n$-vertex input graph are partitioned among $k$ parties, who communicate solely by writing messages on a shared blackboard that is visible to every party. We show that any non-trivial graph problem on $n$-vertex graphs has blackboard communication complexity $\Omega(n)$ bits, even if the edges of the input graph are randomly assigned to the $k$ parties. We say that a graph problem is non-trivial if the output cannot be computed in a model where every party holds at most one edge and no communication is allowed. Our lower bound thus holds for essentially all key graph problems relevant to distributed computing, including Maximal Independent Set (MIS), Maximal Matching, ($\Delta+1$)-coloring, and Dominating Set. In many cases, e.g., MIS, Maximal Matching, and $(\Delta+1)$-coloring, our lower bounds are optimal, up to poly-logarithmic factors.

Item Type: Preprint
Uncontrolled Keywords: cs.DS, cs.DS, cs.DC
Divisions: Faculty of Science and Engineering > School of Electrical Engineering, Electronics and Computer Science
Depositing User: Symplectic Admin
Date Deposited: 25 Mar 2021 08:22
Last Modified: 18 Jan 2023 22:54
Related URLs: