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

Preprint · Yu Cheng, Tianle Jiang, Pachara Sawettamalya, Huacheng Yu

- Archive id: arxiv:2607.05751
- Published: 2026-07-07
- arXiv: https://arxiv.org/abs/2607.05751
- Source URL: https://arxiv.org/abs/2607.05751
- PDF: https://arxiv.org/pdf/2607.05751
- Provenance: arxiv

## Abstract

We revisit several fundamental graph problems in the deterministic two-party communication model. Our main contributions include: (1) a new $\\widetilde{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 and Gabow, our protocol is conceptually simple and avoids the intricacies of finding a maximal set of shortest augmenting paths; (2) a new $\\widetilde{O}(n)$-bit protocol for negative-cycle detection and negative-weight single-source shortest paths. Our protocol simplifies that of Blikstad et al. by replacing a long chain of reductions with a more direct approach based on vertex potentials; (3) a combinatorial $\\widetilde{O}(n)$-bit protocol for computing a maximum matching in bipartite graphs, obtained by reinterpreting the near-linear communication protocol of Blikstad et al. 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.

_Abstract reproduced under CC0-1.0 (arXiv descriptive metadata)._

---
Space Kitty Archive · https://space-kitty.com · API: https://space-kitty.com/api/v1 · MCP: https://space-kitty.com/mcp · Premium: $0.20/request via x402 (Base Sepolia (testnet)). Metadata: arXiv (CC0), OpenAlex (CC0), Europe PMC (CC BY/CC0 works), ClinicalTrials.gov.