Rounded vertex potentials certify exact maximum flow values efficiently
Rounded Potentials Certify Exact Maximum Flow
Data Structures and Algorithms
Summary
Finding the largest amount of flow between two points in a network usually requires complex data per edge. The paper shows that simple numerical labels on each vertex, with a small number of bits, can precisely prove the highest flow possible even in complex graphs. These rounded labels simplify checking and verifying maximum flows and enable faster algorithms for related problems. The authors also demonstrate improved methods for verifying flows in streaming data, distributed systems, and for computing flows between all pairs of nodes.
What this means in practice
- •For network schedulers: Verify maximum flow values in network routing with low memory and communication costs during data streams.
- •For distributed system operators: Use compact vertex-based certificates to check flow constraints efficiently in large distributed networks.
A theory result. No direct application yet.
Authors
Ohad Trabelsi
Abstract
The textbook certificate for maximum flow is lopsided: the cut takes one bit per vertex, while the flow takes one number per edge. Indeed, some graphs have $Θ(n^2)$ terminal pairs for which every maximum flow uses $Θ(n^2)$ edges. Yet we show that one short number per vertex suffices for both cut and flow: $n$ vertex potentials, each rounded to $O(\log(nW))$ bits, certify the exact maximum $st$-flow value in any directed graph with integer capacities at most $W$. Exact potentials can have exponentially large representations. Rounding them may violate flow conservation, but the total error across any cut is less than one unit, so integrality of cut capacities absorbs it. Checking conservation is local and linear in the capacities, allowing the same certificate to yield new bounds in four models (capacities are polynomially bounded unless stated otherwise): - Online annotated streaming. $\widetilde{O}(n)$ total cost (help plus space) for the maximum $st$-flow value, optimal up to logarithmic factors, answering a question of Thaler (ICALP 2016) on whether $o(n^2)$ is possible. - Broadcast proof-labeling. $O(\log(n+p))$-bit labels certifying a maximum $st$-flow value of $p$ in directed and undirected graphs with arbitrary capacities, optimal for $p\ge n^{Ω(1)}$, settling that regime of a question of Korman, Kutten, and Peleg (Distributed Computing 2010). - Merlin-Arthur verification. $\widetilde{O}(n^3)$ time and $O(n^3\log n)$ proof length for directed All-Pairs Max-Flow, improving on previous verification times of $n^{4+o(1)}$ for general capacities and $n^{3.5+o(1)}$ for unit capacities, and answering a question of Akmal (TheoretiCS 2024). - Nondeterministic algorithms. $O(n^{3.614})$ time for directed All-Pairs Max-Flow, or $n^{3.5+o(1)}$ if $ω=2$: the first subquartic bound for general edge capacities, answering a question of Trabelsi (SODA 2025).