 When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.DISC.2018.6
URN: urn:nbn:de:0030-drops-97950
URL: http://drops.dagstuhl.de/opus/volltexte/2018/9795/
 Go to the corresponding LIPIcs Volume Portal

Distributed Approximate Maximum Matching in the CONGEST Model

 pdf-format:

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 (1-epsilon)-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 (1-epsilon)f for bipartite graphs and (1-epsilon) * (g-1)/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 (1-epsilon)* (g-1)/g-approximation for the weighted maximum matching problem in time O(log(Delta W)/epsilon^2 + (log^2(Delta)+log^* n)/epsilon). On the lower-bound 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 2-party communication problem, for which we prove a tight lower bound.

BibTeX - Entry

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:1--6:17},
series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN =	{978-3-95977-092-7},
ISSN =	{1868-8969},
year =	{2018},
volume =	{121},
editor =	{Ulrich Schmid and Josef Widder},
publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
address =	{Dagstuhl, Germany},
URL =		{http://drops.dagstuhl.de/opus/volltexte/2018/9795},
URN =		{urn:nbn:de:0030-drops-97950},
doi =		{10.4230/LIPIcs.DISC.2018.6},
annote =	{Keywords: distributed graph algorithms, maximum matching, deterministic rounding, communication complexity}
}

 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: 28.09.2018

DROPS-Home | Imprint | Privacy 