Rounded Potentials Certify Exact Maximum Flow

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).

Authors

Publication Details

Journal
arXiv (Cornell University)
Published
2026-11-16
DOI
https://doi.org/10.48550/arxiv.2611.20475
Primary Topic
Complexity and Algorithms in Graphs
Type
preprint
Controls
|||
ALL TIME
JAN
FEB
MAR
APR
MAY
JUN
JUL
AUG
SEP
OCT
NOV
preprint

Rounded Potentials Certify Exact Maximum Flow

Ohad Trabelsi
arXiv (Cornell University)
Complexity and Algorithms in Graphs
preprint

Rounded Potentials Certify Exact Maximum Flow

Ohad Trabelsi
preprint en

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).

arXiv (Cornell University)
Complexity and Algorithms in Graphs
AI Navigator

Ask Laika to Summarize, Analyze, and Connect papers live on the map.

Summarize Papers & Methodologies

Extract key findings, datasets, and comparative methods across publications.

Benchmark Rankings & Visual Analytics

Rank top research institutions, authors, funders, topics, and journals by Field-Weighted Citation Impact (FWCI) and paper volume with instant charts.

Connect Distant Disciplines

Bridge topological clusters on the map to find hidden collaborative intersections.

Laika access coming soon