Communication Complexity of Approximate Maximum Matching in Distributed Graph Data
Zengfeng Huang, Božidar Radunović, Milan Vojnović, Qin Zhang · 2013
We consider the problem of computing an approximate maximum matching in a graph that con-sists of n vertices whose edges are stored 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 Ω(α2kn). 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 set-ting, including max-flow and graph sparsification. Other main contribution of this paper is a new approach for multi-party randomized communication complexity for graph problems that is of wide applicability.