  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...[see paper for full abstract]
