On the Communication Complexity of Maximum Matching and Negative-Weight Shortest Paths
This work simplifies known communication protocols for fundamental graph problems, potentially enabling further progress in communication complexity.
The paper presents new communication protocols for maximum matching and negative-weight shortest paths, achieving near-optimal communication costs with simpler constructions. For general graphs, they give an Õ(n^{3/2})-bit protocol for maximum matching, and for bipartite graphs, an Õ(n)-bit protocol. They also provide an Õ(n)-bit protocol for negative-cycle detection and negative-weight single-source shortest paths.
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.