Communication Complexity of Approximate Matching in Distributed Graphs

In this paper we consider the communication complexity of approximation algorithms for max-

imum matching in a graph in the message-passing model of distributed computation. The input

graph consists of n vertices and edges partitioned over a set of k sites.  The output is an α – approximate maximum matching in the input graph which has to be reported by one of the sites.

We show a lower bound on the communication complexity of Ω(α^2 kn) and show that it is tight

up to poly-logarithmic factors. This lower bound also applies to other combinatorial problems on

graphs in the message-passing computation model, including max-flow and graph sparsification.