1 Introduction↩︎

Graph theory is central to computer science, both in theory and in practice. The field studies fundamental problems such as connectivity, shortest paths, matching, spanning forests, and cycle detection. Efficient solutions for these problems form the algorithmic backbone of many computational systems. While the complexity of these problems is well understood in centralized models, much less is known when the input is distributed across players with only partial views of the graph.

In this work, we study the communication complexity of graph problems in the standard two-party model [4]. The edge set of a graph is partitioned between two players, Alice and Bob, who must collaboratively solve a global graph problem while minimizing the amount of communication between them. Although this model is closely related to query, streaming, and distributed models of computation, many fundamental graph problems remain poorly understood from the perspective of communication complexity.

A recent breakthrough of Blikstad et al. [3] showed that maximum bipartite matching and several problems reducible to it admit deterministic protocols using only \(\widetilde{O}(n)\) bits of communication.⁵ At the core of their approach is a cutting-plane framework testing whether a polytope (or feasible region of a linear program (LP)) is empty or has non-trivial volume. This framework is particularly well-suited for the two-party edge-partition model: Given a graph problem \(\mathcal{T}\), one formulates an LP whose feasibility gives the answer to \(\mathcal{T}\), with constraints that are locally checkable and succinctly encodable for communication. The cutting-plane framework is then used to determine the feasibility of this LP, and the result is translated back into an answer for \(\mathcal{T}\).

As a concrete example, Blikstad et al. [3] obtained a near-linear communication protocol for bipartite matching via the dual LP. Specifically, they reduce maximum bipartite matching to testing the feasibility of a vertex cover LP, which can be done using \(O(n\log^2 n)\) bits of communication via the cutting-plane framework.

1.1 Our Contributions↩︎

1.1.1 Maximum Matching in General Graphs↩︎

Given the success of LP-based methods for bipartite graphs, a natural question is whether the same framework can be extended to general (non-bipartite) matching. However, general graphs do not admit a polynomial-size LP formulation with the same clean matching/vertex-cover duality as in bipartite graphs. The standard (primal) LP for non-bipartite matching has exponentially many constraints, so its dual LP has exponentially many variables. This makes it difficult to generalize the volume-based analysis in [3], which is highly sensitive to the dimension of the underlying polytope.

While achieving near-linear communication for general matching appears to require new ideas, we make partial progress by designing a simple protocol for general matching using \(\widetilde{O}(n^{3/2})\) bits of communication.

This \(\widetilde{O}(n^{3/2})\)-bit upper bound is not entirely new: it can also be obtained by simulating the classic \(O(m\sqrt n)\)-time algorithms such as Micali-Vazirani [1] and Gabow [2]. However, these algorithms are quite intricate even in the sequential setting. Although local computation is free in the communication model (which makes sophisticated data structures less of a bottleneck), turning them into explicit communication-efficient protocols still requires a careful implementation of the many steps in these algorithms.

Our main contribution lies in the simplicity of both the protocol and its correctness proof. At a high level, our protocol combines a greedy approach based on the Tutte-Berge formula with a careful simulation of Edmonds’ Blossom algorithm [5]. For the protocol description, it suffices to focus on the problem of deciding whether the input graph has a perfect matching. In the first phase, we maintain the set of low-value Tutte-Berge covers (1) that cover the edges revealed so far, and greedily reveal edges that invalidate as many such covers as possible. The first phase uses \(\widetilde{O}(n^{3/2})\) bits of communication, and either correctly decides that no perfect matching exists, or returns a matching of size \(\frac{n}{2}-\widetilde{O}(\sqrt n)\). In the second phase, we simulate \(\widetilde{O}(\sqrt n)\) rounds of the Blossom algorithm to augment this partial matching to a perfect matching, using another \(\widetilde{O}(n^{3/2})\) bits of communication. It is worth noting that our greedy first phase is conceptually simple and more communication-efficient than directly simulating the Blossom algorithm from scratch (which would require \(\widetilde{O}(n^2)\) bits).

1.1.2 Beyond Bipartite Matching↩︎

We revisit the cutting-plane approach of [3]. By abstracting away the problem-specific aspects of its application to bipartite matching, we show that it provides a general framework for designing communication-efficient protocols for graph problems.

We consider the following four tasks:

• \(\mathsf{Cycle}\): Given an unweighted directed graph, decide whether it contains a directed cycle.

• \(\mathsf{NegativeCycle}\): Given a directed graph with integer weights in \([-W, W]\), decide whether it contains a negative-weight cycle.

• \(\mathsf{SSSP}\): Given a directed graph with integer weights in \([0, W]\) and a source vertex \(s\), compute the shortest-path distances from \(s\) to every vertex \(v\).

• \(\mathsf{NegativeSSSP}\): Given a directed graph with integer weights in \([-W, W]\) and a source vertex \(s\), either detect a negative-weight cycle or, if none exists, compute the shortest-path distances from \(s\) to every vertex \(v\).

Two of these problems admit straightforward near-linear communication protocols via simulations of classical algorithms: \(\mathsf{Cycle}\) can be solved using Kosaraju’s algorithm, and \(\mathsf{SSSP}\) can be solved using Dijkstra’s algorithm. We discuss these simulations in 8 and 9.

The remaining two problems, \(\mathsf{NegativeCycle}\) and \(\mathsf{NegativeSSSP}\), are more challenging due to the presence of negative edge weights. In the sequential setting, both can be solved using the Bellman-Ford algorithm. However, a straightforward simulation of Bellman-Ford requires \(\widetilde{\Omega}(n^2)\) bits in the communication model. To avoid this cost, we apply the cutting-plane framework of [3] to a vertex-potential polytope (which encodes the triangle inequalities for shortest-path distances). This gives a near-linear communication protocol for \(\mathsf{NegativeCycle}\), as we discuss in 4.1. Moreover, a feasible point of this polytope is a key ingredient in our protocol for \(\mathsf{NegativeSSSP}\).

The near-linear communication upper bound for \(\mathsf{NegativeSSSP}\) is not new: it was established in [3]. Their approach, however, proceeds through a chain of reductions, ultimately reducing \(\mathsf{NegativeSSSP}\) to bipartite min-cost \(b\)-matching, which they solve using \(\widetilde{O}(n)\) bits of communication (see 1). These layers of reductions make it difficult to extract a self-contained protocol for \(\mathsf{NegativeSSSP}\) from their work.

Our contribution is a conceptually simple and direct protocol for \(\mathsf{NegativeSSSP}\) that avoids these reductions. At a high level, the protocol computes a feasible point of the vertex-potential polytope used for \(\mathsf{NegativeCycle}\). We then use this point as a proxy for the vertex potentials that would arise in Johnson’s algorithm for all-pairs shortest paths. Reweighting the edges using these potentials essentially yields a communication-efficient reduction from \(\mathsf{NegativeSSSP}\) to \(\mathsf{SSSP}\). Combined with an efficient simulation of Dijkstra’s algorithm, this allows us to recover the exact shortest-path distances using near-linear communication. We describe our approach in detail in 4.2.

1.1.3 Combinatorial Protocol for Bipartite Matching↩︎

We present a combinatorial variant of the near-linear communication protocol for bipartite matching in [3]. Instead of tracking the continuous volume of the vertex-cover polytope, our protocol tracks a discrete analogue: the number of feasible grid points, corresponding to \(\frac{1}{\mathrm{poly}(n)}\)-integral vertex covers. We show that this discrete “volume” is a sufficiently accurate proxy for continuous volume in the analysis. This gives a near-linear communication protocol for bipartite matching whose implementation is purely combinatorial. We discuss this in 5.

1.2 Two-Party Communication Complexity of Graph Problems↩︎

2 Maximum Matching in General Graphs↩︎

The problem of perfect matching in general graphs (\(\mathsf{PM}\)) is defined in the communication model as follows: Alice and Bob are given a disjoint edge partition of a graph \(G=(V,E)\) where \(n = |V|\) is even. Their goal is to determine whether \(G\) has a perfect matching and, if so, to output one.

In this section, we present a deterministic \(\widetilde{O}(n^{3/2})\)-bit communication protocol for \(\mathsf{PM}\).

As a corollary, the protocol can be extended to compute a maximum matching with an additional \(O(\log n)\) factor in communication.

2.0.0.1 A Two-Phase Protocol for Perfect Matching.

We now describe the protocol for 3. Fix an integer parameter \(1 \le k < \frac{n}{2}\) to be optimized later. The protocol proceeds in two phases.

• In Phase 1, Alice and Bob either find a matching of size \(\frac{n}{2}-k\), or correctly conclude that \(G\) has no perfect matching. Phase 1 requires \(O\!\left(\frac{n^2\log^2 n}{k}\right)\) bits of communication.

• In Phase 2, starting from a matching of size \(\frac{n}{2}-k\), Alice and Bob repeatedly find augmenting paths. This requires \(k\) iterations to reach a perfect matching if one exists. By simulating the blossom algorithm [5], each augmenting path can be found using \(O(n\log n)\) bits of communication. Phase 2 requires \(O(kn\log n)\) bits of communication.

Choosing \(k=\Theta(n^{1/2} \log^{1/2} n)\) gives total communication \[O\!\left(\frac{n^2\log^2 n}{k}+kn\log n\right) = O(n^{3/2}\log^{3/2} n),\] which proves 3.

We next describe Phase 1 and analyze its correctness and communication cost in 2.1. The implementation and analysis of Phase 2 are deferred to 6.

2.1 Phase One: Eliminating Tutte-Berge Covers↩︎

In this section, we show how to implement Phase 1 of the protocol.

The key idea is based on the Tutte-Berge formula [19], [20] (4), which gives a min-max characterization of the maximum matching size in general graphs. Motivated by this, we define the notion of Tutte-Berge covers (1), which play a similar role as vertex covers in bipartite graphs: a low-value Tutte-Berge cover of \(G\) certifies that \(G\) cannot have a large matching.

Phase 1 maintains a public graph \(H\subseteq G\) and the set \(\mathcal{C}\) of low-value Tutte-Berge covers that cover \(H\). Alice and Bob repeatedly reveal edges to invalidate covers in \(\mathcal{C}\). If \(\mathcal{C}\) becomes empty, then the Tutte-Berge formula implies that \(H\) has a matching of the target size. If some cover in \(\mathcal{C}\) survives all edges of \(G\), then it certifies that \(G\) has no perfect matching. The main point of the analysis is that, when \(G\) has a perfect matching \(M\), every remaining cover is invalidated by many edges of \(M\), so the players can eliminate covers quickly.

We use the following classical result as a black box.

We now describe Phase 1 of the protocol (3).

The following lemma will be useful for showing that the players can make good progress.

We are now ready to prove the correctness of 3 and analyze the communication cost of simulating it.

3 A Cutting-Plane Framework for Polytope Emptiness Testing↩︎

In this section, we describe a cutting-plane framework for testing whether a polytope is empty. The core idea is closely related to classical optimization techniques such as the center-of-gravity and ellipsoid methods. We do not claim novelty for this framework, as we distill it from [3], where it was used to obtain a near-linear communication protocol for bipartite matching. By abstracting away the problem-specific aspects of bipartite matching, we present it as a general framework that can be applied to other communication problems.

Consider the following “emptiness-testing” problem: given a convex polytope \(P \subseteq \mathbb{R}^n\) via a separation oracle, we are promised that either \(P = \varnothing\) or \(\operatorname{vol}(P) \ge \tau\) for some known volume threshold \(\tau > 0\). The goal is to determine which of the two cases holds using a small number of queries to the separation oracle of \(P\).

We defer the proof of 3 to 7. 3 suggests the following general recipe for solving a graph problem \(\mathcal{T}\) via polytope emptiness testing:

1. Reformulate a relevant (sub)problem as testing whether a convex polytope \(P\) is empty or has volume at least \(\tau\), for appropriate choices of \(P\) and \(\tau\).

2. Show that a separation oracle for \(P\) can be efficiently simulated in the communication model.

3. Apply 4 to distinguish between \(P = \varnothing\) and \(\operatorname{vol}(P) \ge \tau\).

4. Translate the outcome back to the original problem \(\mathcal{T}\).

This recipe is particularly well-suited for the two-party model. Primal LP formulations of many graph problems (e.g., bipartite matching or shortest paths) have variables corresponding to edges, which are not jointly known by the players. The key observation is that the dual LPs often have one constraint per edge. In many cases, each player can locally check the constraints corresponding to their own edges, and a violated constraint can be encoded by a short message.

As concrete examples, [3] applied this framework to a fractional vertex-cover polytope (the dual of fractional matching). By Kőnig’s theorem, this polytope is empty if and only if the input graph has a perfect matching (see 5.1). In 4, we apply the same framework to a vertex-potential polytope (the dual of shortest paths) to obtain new communication protocols for negative cycle detection and negative-weight SSSP.

4 Negative Cycle Detection and Negative-Weight Shortest Paths↩︎

4.1 Negative Cycle Detection↩︎

The problem of negative cycle detection (\(\mathsf{NegativeCycle}\)) is defined as follows: Alice and Bob are given a disjoint edge partition of a directed weighted graph \(G = (V, E, w)\) with integer edge weights in \([-W, W]\). Their goal is to decide whether \(G\) has a negative cycle.

Let \(n = |V|\). We consider the following vertex-potential polytope, whose constraints encode approximate triangle inequalities. \[\label{eqn:triangle-ineq-polytope} P^{\triangle}(G) := \left\{ x \in \mathbb{R}^n \; \middle| \; \begin{align} &x_v - x_u \le w(u, v) + \tfrac{1}{n^2} && \forall (u,v) \in E \\ &0 \le x_v \le nW && \forall v \in V \end{align} \right\}.\tag{1}\]

The additive \(\frac{1}{n^2}\) slack will allow us to lower bound the volume of \(P^{\triangle}(G)\) when it is nonempty. At the same time, for integer edge weights, this slack does not affect negative-cycle detection: we show that \(P^{\triangle}(G)\) is empty if and only if \(G\) has a negative cycle.

We now present our protocol for \(\mathsf{NegativeCycle}\). Note that when \(G\) has no negative cycles, the protocol outputs a vector \(p \in P^{\triangle}(G)\), which we will use in 4.2 to solve \(\mathsf{NegativeSSSP}\).

4.2 Negative-Weight Single-Source Shortest Paths↩︎

The problem of negative-weight single-source shortest paths (\(\mathsf{NegativeSSSP}\)) is defined as follows: Alice and Bob are given a disjoint edge partition of a directed weighted graph \(G = (V, E, w)\) with integer edge weights in \([-W, W]\), and a source vertex \(s\in V\). Their goal is to either decide that \(G\) has a negative cycle or compute the single-source shortest-path distances \(d_G(s,v)\) for all \(v\in V\).

We use a vertex-potential reweighting idea, familiar from Johnson’s algorithm for all-pairs shortest paths [21]. For a function \(\phi: V \to \mathbb{R}\), let \[w_\phi(u,v) := w(u,v) + \phi(u) - \phi(v), \qquad \forall (u,v) \in E,\] and let \(G_\phi := (V, E, w_\phi)\). Along any path from \(s\) to \(v\), the \(\phi(\cdot)\) terms telescope. Taking the minimum over all \(s\)-\(v\) paths shows \[d_{G_\phi}(s,v) = d_G(s,v) + \phi(s) - \phi(v) \qquad \forall v \in V.\] In particular, if \(w_\phi(e) \ge 0\) for every edge \(e \in E\), one can compute \(d_{G_\phi}(s, \cdot)\) using any nonnegative-weight shortest-path algorithm and recover \(d_G(s,v)\).

In our application, setting \(\phi\) to the vector \(p \in P^{\triangle}(G)\) returned by 5 only guarantees \(w_\phi(u, v) \ge -\frac{1}{n^2}\). To obtain nonnegative edge weights, we round \(w_\phi(u, v)\) up to the nearest multiple of \(\frac{1}{n}\). This rounding has only a mild effect on shortest-path distances: it increases the weight of any single edge by at most \(\frac{1}{n}\) and the weight of any simple path by at most \(\frac{n-1}{n} < 1\). Since \(d_G(s,v)\) is an integer, we can then run a nonnegative-weight shortest-path algorithm and recover the original distances by taking floors at the end.⁸

We conclude this section with a deterministic protocol for \(\mathsf{NegativeSSSP}\).

5 Maximum Matching in Bipartite Graphs↩︎

In this section, we first restate the \(O(n \log^2 n)\)-bit protocol in [3] for bipartite matching, and then we present our combinatorial protocol (resulted from discretizing the said work) in 5.2.

5.1 A Near-Linear Communication Protocol for Bipartite Matching↩︎

In the problem of bipartite perfect matching (\(\mathsf{BPM}\)), Alice and Bob are given a disjoint edge partition of an undirected bipartite graph \(G = (V, E)\). Their goal is to decide whether \(G\) admits a perfect matching and output one if it does. We assume without loss of generality that \(n = |V|\) is even and that each side of \(G\) has exactly \(\frac{n}{2}\) vertices. The breakthrough result of [3] gave a protocol for this problem with near-linear communication complexity.

We briefly describe the protocol from [3], before sketching a proof for 7.

Consider the following vertex-cover polytope of \(G\): \[\label{eqn:fractional95VC95polytope} P^{\textrm{VC}}(G) := \left\{ x \in \mathbb{R}^n \; \middle| \; \begin{align} \, & x_u + x_v \ge 1 && \forall (u, v) \in E, \\ \, & \textstyle\sum_{v\in V} x_v \le \frac{n}{2} - \frac{1}{2}, \\ \, & 0\le x_v \le 1 && \forall v \in V \end{align} \right\}.\tag{3}\]

The following lemma is from [3]. For completeness, we provide its proof in 10.

5.2 A Combinatorial Protocol for Bipartite Perfect Matching↩︎

The cutting-plane framework (4) is inherently continuous: it operates over a polytope, tracks progress using its volume, and computes the center of mass to find a violated constraint that eliminates a constant fraction of the volume. In this section, we present a combinatorial protocol for \(\mathsf{BPM}\) that avoids these continuous operations.

Our idea is to discretize the vertex-cover polytope \(P^{\textrm{VC}}(G)\). Consider a set of fractional vertex covers \(Q^{\textrm{VC}}(G)\) defined as follows: \[\label{eqn:fractional95VC95lattice} Q^{\textrm{VC}}(G) := \left\{ x \in \mathbb{R}^n \; \middle| \; \begin{align} \, & x_u + x_v \ge 1 && \forall (u, v) \in E, \\ \, & \textstyle\sum_{v\in V} x_v \le \frac{n}{2} - \frac{1}{2}, \\ \, & x_v \in \left\{0, \tfrac{1}{d}, \ldots, 1\right\} && \forall v \in V \end{align} \right\}.\tag{4}\]

We say that a nonnegative vector in \(\mathbb{R}^n\) is \(d\)-uniform if each of its coordinates is a multiple of \(\frac{1}{d}\). With this notation, \(Q^{\textrm{VC}}(G)\) is the set of \(d\)-uniform fractional vertex covers of \(G\) of size at most \(\frac{n}{2}-\frac{1}{2}\). For sufficiently large \(d = \mathrm{poly}(n)\), the discrete quantity \(|Q^{\textrm{VC}}(H)|\) is essentially proportional to \(\operatorname{vol}(P^{\textrm{VC}}(H))\) throughout the protocol. As the players communicate edges and add them to a shared public graph, we can use this discrete quantity as a proxy for volume to measure progress.

We formally state our protocol for \(\mathsf{BPM}\) in 5.

We defer the proof of [lem:discrete95BMM95progress] to 10.1 and first use it to prove 8.

6 Finding Augmenting Paths via the Blossom Algorithm↩︎

Fix an arbitrary matching \(M \subseteq E\). An augmenting path is a path in \(G\) that begins and ends at distinct unmatched vertices, and alternates between edges not in \(M\) and edges in \(M\). By flipping the matching status of each edge along such a path, we increase the size of the matching by one. The following fact about augmenting paths is standard.

In this section, we describe a procedure for finding an augmenting path in general graphs using \(O(n \log n)\) bits. Hence, by repeating the process (up to) \(k\) times starting from a matching of size \(\frac{n}{2}-k\) obtained from Phase 1, one can obtain a maximum matching.

To identify an augmenting path, we follow Edmonds’ Blossom Algorithm [5] by constructing a maximal alternating forest. Initially, the forest is empty, and all vertices are marked as “U” (unvisited). The forest grows from the unmatched vertices as roots by alternately exploring unmatched and matched edges. Each vertex, once added to the forest, is dynamically re-labeled based on the parity of its distance from its root: vertices at even distances are marked “E”, and those at odd distances are marked “O”. For convenience, we refer to an edge \((a, b)\) as an E-O edge if \(a\) is marked “E” and \(b\) is marked “O”. This notation extends analogously to other type combinations. The primary goal is to incrementally grow a maximal alternating forest and assign parity labels to vertices such that no E-U edge remains in the graph (hence the term “maximal”). An example of such a maximal alternating forest is illustrated in 6.

1. Mark every unmatched vertex as “E”; these vertices are also the roots of the alternating forest. Mark all remaining vertices as “U”. Let \(F\) denote an edge set that is initially empty.

2. Repeat the following steps until no E-U edge remains in \(G\):

   1. Pick any E-U edge \((a, b) \in G \setminus F\).

   2. Add edge \((a, b)\) to \(F\) and label vertex \(b\) as “O”.

   3. Let \(b'\) be the unique neighbor of \(b\) such that \((b, b') \in M\). Note that such a \(b'\) must exist, as otherwise \(b\) would have been unmatched and thus labeled “E” in Step 1.

   4. Add edge \((b, b')\) to \(F\) and label vertex \(b'\) as “E”.

3. To be continued.

Such a process can be efficiently simulated in the setting of two-party communication. It requires only one of the players to locally identify their E-U edge and communicate it to the other player. The remaining steps of the procedure can be executed jointly.

Following this procedure, some vertices are re-labeled according to their parity in the alternating forest \(F\). At the end of this phase, no E-U edges remain in the graph \(G\). The following fact captures an important structural consequence of this property.

This fact allows us to continue the algorithm. If we are able to find an E-E edge in the graph, we proceed by adding it to the alternating forest. One of two outcomes will then occur (demonstrated in 7):

• We discover an augmenting path, in which case the algorithm terminates successfully.

• We encounter a structure known as a blossom—an odd-length cycle that includes exactly one vertex, called the tip, which is incident to two non-matching edges, while the remaining edges of the cycle alternate between matched and unmatched edges.

We emphasize the latter scenario. Blossoms are useful objects because they preserve the existence of augmenting paths even when contracted into a single supervertex. The following fact formalizes this intuition:

With this fact in mind, the algorithm proceeds to:

3. Attempt to find an E-E edge \((a,b) \in G \setminus F\).

   1. If no such E-E edge exists, terminate and confirm that \(M\) is a maximum matching.

   2. If \((a,b)\) is an E-E edge and \(a\) and \(b\) lie in alternating trees with different roots, then an augmenting path is found. Terminate and augment \(M\).

   3. If \((a,b)\) is an E-E edge and both vertices share the same tree root, then a blossom is found. Contract this blossom into a single supervertex (with the tip as its representative), and assign it the label “E”. Note that this contraction may introduce new E-U edges. Recurse to Step (2) to continue growing the maximal alternating forest on the contracted graph.

Similar to before, this process only requires the players to locally identify an E-E edge and communicate it to the other player. Then, upon terminating via Step (3b), among the edges revealed so far, there must exist an augmenting path wrt. \(M\), and both players can locally find a consistent augmenting path and augment \(M\).

6.1 Analysis↩︎

Correctness follows from the standard analysis of the blossom algorithm. We focus on bounding the communication cost.

We claim that the following potential function never increases during the execution of the algorithm before reaching Step (3a) or Step (3b) after which it terminates. \[\begin{align} \Phi \;:= & \;\underbrace{(\text{\# edges communicated})}_{\Phi_1} \;+ \;\underbrace{(\text{\# unmarked vertices})}_{\Phi_2} \;+ \;\underbrace{(n - \text{\# blossoms contracted})}_{\Phi_3}. \end{align}\]

To justify this, we examine the two key steps where the potential may change:

• In Step 2, whenever an E-U edge is revealed by one player, two new vertices are marked. Hence, \(\Phi_1\) increases by \(1\) and \(\Phi_2\) decreases by \(2\), so \(\Phi\) decreases by \(1\).

• In Step 3c, when an E-E edge with the same root is found, this completes a blossom. One edge is communicated to complete the cycle, increasing \(\Phi_1\) by 1. The number of blossoms also increases by 1, reducing \(\Phi_3\) by 1. Thus, the net change in \(\Phi\) is zero.

Initially, no edges have been communicated, at most \(n\) vertices are unmarked, and no blossoms have been contracted. Thus, the starting potential is \(\Phi \leq 2n\) and afterwards it only increases by one if the algorithm terminates via Step (3b). At termination, the number of edges communicated is exactly \(\Phi_1\). Moreover, the number of unmarked vertices is nonnegative (i.e., \(\Phi_2 \geq 0\)), and the number of blossoms is at most \(n\) (i.e., \(\Phi_3 \geq 0\)), as each blossom reduces the number of supervertices by at least one. Thus, the number of edges communicated is bounded by \(\Phi_1 \leq \Phi \leq 2n+1\). Since each communicated edge requires \(O(\log n)\) bits to describe, this implies the procedure of finding an augmenting path can be simulated using \(O(n \log n)\) bits of communication between Alice and Bob.

7 Omitted Proofs from Section 3↩︎

8 Directed Cycle Detection↩︎

The problem of directed cycle detection (\(\mathsf{Cycle}\)) is defined as follows: the players are given an edge partition of a directed graph \(G = (V, E)\) without self-loops and with \(n = |V|\). Their goal is to determine whether \(G\) contains a directed cycle.

We simulate Kosaraju’s algorithm to compute all strongly connected components (SCCs) of \(G\). Recall that Kosaraju’s algorithm performs two depth-first searches (DFS). We first discuss how to simulate DFS on a directed graph with a specific vertex ordering (8).

In Line [line:dfs-check-vu], we simulate the loop over \(v\)’s edges as follows: Alice repeatedly checks her remaining (unchecked) edges \((v,u)\) for one with \(u\) unvisited; each time she finds one, she sends it to Bob, and both proceed to the recursive \(\Search\) call in Line [line:dfs95inner95call] before returning to check her remaining edges. Once she has exhausted all her edges leaving \(v\), she sends a single “done” message, and then it is Bob’s turn to do the same with his edges. Once Bob exhausts his edges and sends “done”, they backtrack at Line [line:dfs95return]. Both players maintain a correct copy of the \(\Visited\) array. For each vertex, each player sends exactly one “done” message. Each communicated edge leads to an unvisited vertex, which is immediately marked as visited, so at most \(n-1\) edges are communicated in total. Each edge requires \(O(\log n)\) bits to encode, so the total communication for one DFS is \(O(n \log n)\) bits.

We now build on this to discuss how to simulate Kosaraju’s algorithm.

9 Nonnegative-Weight Single-Source Shortest Paths↩︎

The problem of single-source shortest paths (\(\mathsf{SSSP}\)) is as follows: the players are given a disjoint edge partition of a directed weighted graph \(G = (V, E, w)\) whose weights are integers in \([0, W]\), and a source vertex \(s \in V\). Their goal is to compute the shortest path distance \(d_G(s,v)\) from \(s\) to every vertex \(v \in V\).

We show that Dijkstra’s algorithm can be simulated using \(O(n\log(nW))\) bits of communication. For simplicity, we first recall a basic version of Dijkstra’s algorithm without a priority queue.

10 Omitted Proofs from Section 5↩︎

10.1 Proof of Lemma [lem:discrete95BMM95progress]↩︎

We first introduce the notion of a balanced polytope.

Given a bipartite graph \(G = (V, E)\), recall that we define \(P^{\textrm{VC}}(G)\) and \(Q^{\textrm{VC}}(G)\) as follows: \[\begin{align} P^{\textrm{VC}}(G) &:= \left\{ x \in \mathbb{R}^n \; \middle| \; \begin{aligned} \, & x_u + x_v \ge 1 && \forall (u, v) \in E, \\ \, & \textstyle\sum_{v\in V} x_v \le \frac{n}{2} - \frac{1}{2}, \\ \, & 0\le x_v \le 1 && \forall v \in V \end{aligned} \right\} \\ Q^{\textrm{VC}}(G) &:= \left\{ x \in \mathbb{R}^n \; \middle| \; \begin{align} \, & x_u + x_v \ge 1 && \forall (u, v) \in E, \\ \, & \textstyle\sum_{v\in V} x_v \le \frac{n}{2} - \frac{1}{2}, \\ \, & x_v \in \left\{0, \tfrac{1}{d}, \ldots, 1\right\} && \forall v \in V \end{align} \right\}. \end{align}\]

A key observation is that every non-empty vertex-cover polytope is \(\frac{1}{8n}\)-balanced. 2 follows directly from the proof of [lem:P95vertex].

The following lemma states that if the grid has sufficiently fine resolution, the volume of a balanced polytope can be well approximated by the (scaled) number of grid points it contains. We prove [lem:approx95volume] in 10.2.

The following fact is immediate from the definitions of \(P^{\textrm{VC}}(G)\) and \(Q^{\textrm{VC}}(G)\).

We are now ready to prove [lem:discrete95BMM95progress].

10.2 Proof of Lemma [lem:approx95volume]↩︎

For any pair of points \(a, b \in \mathbb{R}^n\), we denote by \(ab\) the line segment with endpoints \(a\) and \(b\), and by \(|ab|\) its Euclidean length. For an affine hyperplane \(H\), let \(d(a, H)\) denote the distance from point \(a\) to \(H\). This is equal to \(|az|\), where \(z\) is the orthogonal projection of \(a\) onto \(H\). When \(F\) is a facet of a polytope, we write \(d(a,F)\) for the distance from \(a\) to the supporting hyperplane of \(F\).

Now we prove our volume approximation lemma.

References↩︎

---

1. Brown University. [yu_cheng@brown.edu](yu_cheng@brown.edu){.uri}. Supported in part by NSF Award CCF-2307106.↩︎

2. Duke University. [tianle.jiang@duke.edu](tianle.jiang@duke.edu){.uri}. Supported in part by NSF Award IIS-2402823. Part of the work was done while visiting Brown University.↩︎

3. Princeton University. [ps3122@princeton.edu](ps3122@princeton.edu){.uri}. Supported in part by NSF CAREER Award CCF-2339942.↩︎

4. Princeton University. [yuhch123@gmail.com](yuhch123@gmail.com){.uri}. Supported in part by NSF CAREER Award CCF-2339942.↩︎

5. Throughout this paper, we use \(\widetilde{O}(\cdot)\) to hide \(\mathrm{polylog}(n)\) factors.↩︎

6. Given a size-\(r\) matching in \(G\), the remaining \(n-2r\) original vertices can be matched to the auxiliary vertices. Conversely, a perfect matching of \(G_r\) matches each auxiliary vertex to a distinct original vertex, leaving exactly \(2r\) original vertices to be matched among themselves.↩︎

7. For a Tutte-Berge cover \(C\), we can increase \(\delta(C)\) by \(1\) without reducing its edge coverage, e.g., by moving a size-\(1\) odd set into \(A\) or moving two vertices from a larger odd set into \(A\).↩︎

8. Analogous rounding arguments appear in the near-linear-time algorithm of [22] for negative-weight SSSP.↩︎

9. Specifically, Grünbaum [23] showed that for any convex body \(K\) and any halfspace \(H\) that does not contain the center of mass of \(K\), \(\operatorname{vol}(K \cap H) \le \left(1 - \frac{1}{e}\right) \operatorname{vol}(K)\).↩︎