Ahmadi, Mohamad ;
Kuhn, Fabian ;
Oshman, Rotem
Distributed Approximate Maximum Matching in the CONGEST Model
Abstract
We study distributed algorithms for the maximum matching problem in the CONGEST model, where each message must be bounded in size. We give new deterministic upper bounds, and a new lower bound on the problem.
We begin by giving a distributed algorithm that computes an exact maximum (unweighted) matching in bipartite graphs, in O(n log n) rounds. Next, we give a distributed algorithm that approximates the fractional weighted maximum matching problem in general graphs. In a graph with maximum degree at most Delta, the algorithm computes a (1epsilon)approximation for the problem in time O(log(Delta W)/epsilon^2), where W is a bound on the ratio between the largest and the smallest edge weight. Next, we show a slightly improved and generalized version of the deterministic rounding algorithm of Fischer [DISC '17]. Given a fractional weighted maximum matching solution of value f for a given graph G, we show that in time O((log^2(Delta)+log^*n)/epsilon), the fractional solution can be turned into an integer solution of value at least (1epsilon)f for bipartite graphs and (1epsilon) * (g1)/g * f for general graphs, where g is the length of the shortest odd cycle of G. Together with the above fractional maximum matching algorithm, this implies a deterministic algorithm that computes a (1epsilon)* (g1)/gapproximation for the weighted maximum matching problem in time O(log(Delta W)/epsilon^2 + (log^2(Delta)+log^* n)/epsilon).
On the lowerbound front, we show that even for unweighted fractional maximum matching in bipartite graphs, computing an (1  O(1/sqrt{n}))approximate solution requires at least Omega~(D+sqrt{n}) rounds in CONGEST. This lower bound requires the introduction of a new 2party communication problem, for which we prove a tight lower bound.
BibTeX  Entry
@InProceedings{ahmadi_et_al:LIPIcs:2018:9795,
author = {Mohamad Ahmadi and Fabian Kuhn and Rotem Oshman},
title = {{Distributed Approximate Maximum Matching in the CONGEST Model}},
booktitle = {32nd International Symposium on Distributed Computing (DISC 2018)},
pages = {6:16:17},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959770927},
ISSN = {18688969},
year = {2018},
volume = {121},
editor = {Ulrich Schmid and Josef Widder},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2018/9795},
URN = {urn:nbn:de:0030drops97950},
doi = {10.4230/LIPIcs.DISC.2018.6},
annote = {Keywords: distributed graph algorithms, maximum matching, deterministic rounding, communication complexity}
}
04.10.2018
Keywords: 

distributed graph algorithms, maximum matching, deterministic rounding, communication complexity 
Seminar: 

32nd International Symposium on Distributed Computing (DISC 2018)

Issue date: 

2018 
Date of publication: 

04.10.2018 