Communication Complexity of Approximate Matching in Distributed Graphs
Zengfeng Huang, Božidar Radunović, Milan Vojnović, Qin Zhang · DROPS (Schloss Dagstuhl – Leibniz Center for Informatics) · 2015
In this paper we consider the communication complexity of approximation algorithms for maximum 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 \alpha-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 \Omega(\alpha^2 k n) 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.