DROPS

Document

DOI: 10.4230/LIPIcs.ESA.2026.72

On the Communication Complexity of Maximum Matching and Negative-Weight Shortest Paths

Authors: Yu Cheng, Tianle Jiang, Pachara Sawettamalya, and Huacheng Yu

Published in: LIPIcs, Volume 388, 34th Annual European Symposium on Algorithms (ESA 2026)

Abstract

We revisit several fundamental graph problems in the deterministic two-party communication model. Our main contributions include: - We give a new Õ(n^{3/2})-bit protocol for computing a maximum matching in general graphs. While the same upper bound can be obtained by simulating the classic algorithms of Micali-Vazirani [Silvio Micali and Vijay V. Vazirani, 1980] and Gabow [Harold N. Gabow, 2017], our protocol is conceptually simple and avoids the intricacies of finding a maximal set of shortest augmenting paths. - We give a new Õ(n)-bit protocol for negative-cycle detection and negative-weight single-source shortest paths. Our protocol simplifies that of Blikstad et al. [Joakim Blikstad et al., 2022] by replacing a long chain of reductions with a more direct approach based on vertex potentials. - We give a combinatorial Õ(n)-bit protocol for computing a maximum matching in bipartite graphs, obtained by reinterpreting the near-linear communication protocol of Blikstad et al. [Joakim Blikstad et al., 2022] through a discretized analysis. Together, these results provide simpler protocols for several basic graph problems. We hope they will inspire further advances on the communication complexity of a wide range of graph problems.

Cite as

Yu Cheng, Tianle Jiang, Pachara Sawettamalya, and Huacheng Yu. On the Communication Complexity of Maximum Matching and Negative-Weight Shortest Paths. In 34th Annual European Symposium on Algorithms (ESA 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 388, pp. 72:1-72:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{cheng_et_al:LIPIcs.ESA.2026.72,
  author =	{Cheng, Yu and Jiang, Tianle and Sawettamalya, Pachara and Yu, Huacheng},
  title =	{{On the Communication Complexity of Maximum Matching and Negative-Weight Shortest Paths}},
  booktitle =	{34th Annual European Symposium on Algorithms (ESA 2026)},
  pages =	{72:1--72:22},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-445-1},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{388},
  editor =	{Bille, Philip and Pettie, Seth and Storandt, Sabine},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2026.72},
  URN =		{urn:nbn:de:0030-drops-272086},
  doi =		{10.4230/LIPIcs.ESA.2026.72},
  annote =	{Keywords: Graph algorithms, communication complexity, maximum matching, negative-weight shortest paths}
}

Search Results

Documents authored by Jiang, Tianle

On the Communication Complexity of Maximum Matching and Negative-Weight Shortest Paths

Abstract

Cite as

Thanks for your feedback!

Could not send message