When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.STACS.2015.460
URN: urn:nbn:de:0030-drops-49348
URL: http://drops.dagstuhl.de/opus/volltexte/2015/4934/
 Go to the corresponding LIPIcs Volume Portal

### Communication Complexity of Approximate Matching in Distributed Graphs

 pdf-format:

### Abstract

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.

### BibTeX - Entry

@InProceedings{huang_et_al:LIPIcs:2015:4934,
author =	{Zengfeng Huang and Bozidar Radunovic and Milan Vojnovic and Qin Zhang},
title =	{{Communication Complexity of Approximate Matching in Distributed Graphs}},
booktitle =	{32nd International Symposium on Theoretical Aspects of Computer Science (STACS 2015)},
pages =	{460--473},
series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN =	{978-3-939897-78-1},
ISSN =	{1868-8969},
year =	{2015},
volume =	{30},
editor =	{Ernst W. Mayr and Nicolas Ollinger},
publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},