Speaker
Description
Amir Azarmehr and Soheil Behnezhad
Abstract: We study the robust communication complexity of maximum matching. Edges of an arbitrary
n-vertex graph G are randomly partitioned between Alice and Bob independently and uniformly.
Alice has to send a single message to Bob such that Bob can find an (approximate) maximum
matching of the whole graph G. We specifically study the best approximation ratio achievable
via protocols where Alice communicates only O~(n) bits to Bob.
There has been a growing interest on the robust communication model due to its connections
to the random-order streaming model. An algorithm of Assadi and Behnezhad [ICALP’21]
implies a (2/3 + ε_0 ∼ .667)-approximation for a small constant 0 < ε_0 < 10^{−18}, which remains
the best-known approximation for general graphs. For bipartite graphs, Assadi and Behnezhad
[Random’21] improved the approximation to .716 albeit with a computationally inefficient (i.e.,
exponential time) protocol.
In this paper, we study a natural and efficient protocol implied by a random-order streaming
algorithm of Bernstein [ICALP’20] which is based on edge-degree constrained subgraphs (EDCS)
[Bernstein and Stein; ICALP’15]. The result of Bernstein immediately implies that this pro-
tocol achieves an (almost) (2/3 ∼ .666)-approximation in the robust communication model.
We present a new analysis, proving that it achieves a much better (almost) (5/6 ∼ .833)-
approximation. This significantly improves previous approximations both for general and bi-
partite graphs. We also prove that our analysis of Bernstein’s protocol is tight.