Projects per year
Abstract
The message complexity of a distributed algorithm is the total number of messages sent by all nodes over the course of the algorithm. This paper studies the message complexity of distributed algorithms for fundamental graph optimization problems. We focus on four classical graph optimization problems: Maximum Matching (MaxM), Minimum Vertex Cover (MVC), Minimum Dominating Set (MDS), and Maximum Independent Set (MaxIS). In the sequential setting, these problems are representative of a wide spectrum of hardness of approximation. While there has been some progress in understanding the round complexity of distributed algorithms (for both exact and approximate versions) for these problems, much less is known about their message complexity and its relation with the quality of approximation. We almost fully quantify the message complexity of distributed graph optimization by showing the following results: 1. Cubic regime: Our first main contribution is showing essentially cubic, i.e., (n3) lower bounds1 (where n is the number of nodes in the graph) on the message complexity of distributed exact computation of Minimum Vertex Cover (MVC), Minimum Dominating Set (MDS), and Maximum Independent Set (MaxIS). Our lower bounds apply to any distributed algorithm that runs in polynomial number of rounds (a mild and necessary restriction). Our result is significant since, to the best of our knowledge, this are the first ω(m) (where m is the number of edges in the graph) message lower bound known for distributed computation of such classical graph optimization problems. Our bounds are essentially tight, as all these problems can be solved trivially using O(n3) messages in polynomial rounds. All these bounds hold in the standard CONGEST model of distributed computation in which messages are of O(log n) size. 2. Quadratic regime: In contrast, we show that if we allow approximate computation then θ(n2) messages are both necessary and sufficient. Specifically, we show that (n2) messages are required for constantfactor approximation algorithms for all four problems. For MaxM and MVC, these bounds hold for any constantfactor approximation, whereas for MDS and MaxIS they hold for any approximation factor better than some specific constants. These lower bounds hold even in the LOCAL model (in which messages can be arbitrarily large) and they even apply to algorithms that take arbitrarily many rounds. We show that our lower bounds are essentially tight, by showing that if we allow approximation to within an arbitrarily small constant factor, then all these problems can be solved using O(n2) messages even in the CONGEST model. 3. Linear regime: We complement the above lower bounds by showing distributed algorithms with O (n) message complexity that run in polylogarithmic rounds and give constantfactor approximations for all four problems on random graphs. These results imply that almost linear (in n) message complexity is achievable on almost all (connected) graphs of every edge density.
Original language  English 

Title of host publication  15th Innovations in Theoretical Computer Science Conference, ITCS 2024 
Editors  Venkatesan Guruswami 
Publisher  Schloss Dagstuhl  LeibnizZentrum für Informatik 
ISBN (Electronic)  9783959773096 
DOIs  
Publication status  Published  2024 
MoE publication type  A4 Conference publication 
Event  Innovations in Theoretical Computer Science Conference  Berkeley, United States Duration: 30 Jan 2024 → 2 Feb 2024 Conference number: 15 
Publication series
Name  Leibniz International Proceedings in Informatics, LIPIcs 

Volume  287 
ISSN (Print)  18688969 
Conference
Conference  Innovations in Theoretical Computer Science Conference 

Abbreviated title  ITCS 
Country/Territory  United States 
City  Berkeley 
Period  30/01/2024 → 02/02/2024 
Keywords
 distributed approximation
 Distributed graph algorithm
 message complexity
Fingerprint
Dive into the research topics of 'The Message Complexity of Distributed Graph Optimization'. Together they form a unique fingerprint.Projects
 1 Active

: Massively Parallel Algorithms for LargeScale Graph Problems
Uitto, J. (Principal investigator), Cambus, M. (Project Member), Latypov, R. (Project Member) & Pai, S. (Project Member)
01/09/2020 → 27/04/2025
Project: Academy of Finland: Other research funding