### Technical Report No. 286 - Abstract

Mohamad Ahmadi, Fabian Kuhn und Rotem Oshman
*Distributed Approximate Maximum Matching in the CONGEST Model*

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-eps)-approximation for the problem in time O(log(Delta W)/eps^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)/eps), the fractional solution can be turned into an integer solution of value at least (1-eps)f for bipartite graphs and (1-\eps) * (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-eps)*(g-1)/g-approximation for the weighted maximum matching problem in time O(log(Delta W)/eps^2 + (log^2(Delta)+log^* n)/eps).

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 \tilde{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.

Report No. 286 (PDF)