{"ID":6023335,"CreatedAt":"2026-07-08T01:00:23.257252134Z","UpdatedAt":"2026-07-10T01:44:12.350457273Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2607.05751","arxiv_id":"2607.05751","title":"On the Communication Complexity of Maximum Matching and Negative-Weight Shortest Paths","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.","short_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-...","url_abs":"https://arxiv.org/abs/2607.05751","url_pdf":"https://arxiv.org/pdf/2607.05751v1","authors":"[\"Yu Cheng\",\"Tianle Jiang\",\"Pachara Sawettamalya\",\"Huacheng Yu\"]","published":"2026-07-07T02:11:55Z","proceeding":"cs.DS","tasks":"[\"cs.DS\",\"cs.CC\"]","methods":"[]","has_code":false}