Communication Complexity of Approximate Maximum Matching in Distributed Graph Data

We consider the problem of computing an approximate maximum matching in a graph that consists of n vertices whose edges are stored partitioned across k distributed sites in a data center. We are interested in characterizing the communication complexity of this problem which is of primary concern in data centers where communication bandwidth is a scarce resource. Our main result is that any algorithm that finds an α-approximate maximum matching has a communication complexity of Ω(α² k n). Perhaps surprisingly, we show that this lower bound matches an upper bound of a simple sequential algorithm, showing that no benefits can be obtained with respect to the communication cost despite the full flexibility allowed by the underlying computation model. Our lower bound for matching also implies lower bounds for other important graph problems in the distributed computation setting, including max-flow and graph sparsification. Other main contribution of this paper is a new technique for multi-party randomized communication complexity that is of wide applicability.