betaFeedback

WorksComputer Science

Rounded Potentials Certify Exact Maximum Flow

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 Θ(n2)Θ(n^2) terminal pairs for which every maximum flow uses Θ(n2)Θ(n^2) edges. Yet we show that one short number per vertex suffices for both cut and flow: nn vertex potentials, each rounded to O(log⁡(nW))O(\log(nW)) bits, certify the exact maximum stst-flow value in any directed graph with integer capacities at most WW. 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. O~(n)\widetilde{O}(n) total cost (help plus space) for the maximum stst-flow value, optimal up to logarithmic factors, answering a question of Thaler (ICALP 2016) on whether o(n2)o(n^2) is possible. - Broadcast proof-labeling. O(log⁡(n+p))O(\log(n+p))-bit labels certifying a maximum stst-flow value of pp in directed and undirected graphs with arbitrary capacities, optimal for p≥nΩ(1)p\ge n^{Ω(1)}, settling that regime of a question of Korman, Kutten, and Peleg (Distributed Computing 2010). - Merlin-Arthur verification. O~(n3)\widetilde{O}(n^3) time and O(n3log⁡n)O(n^3\log n) proof length for directed All-Pairs Max-Flow, improving on previous verification times of n4+o(1)n^{4+o(1)} for general capacities and n3.5+o(1)n^{3.5+o(1)} for unit capacities, and answering a question of Akmal (TheoretiCS 2024). - Nondeterministic algorithms. O(n3.614)O(n^{3.614}) time for directed All-Pairs Max-Flow, or n3.5+o(1)n^{3.5+o(1)} if ω=2ω=2: the first subquartic bound for general edge capacities, answering a question of Trabelsi (SODA 2025).

Paper details

vlnc:W_hjd8zcyc
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
arXiv nonexclusive license
Usage

views · 1

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Computer Science

Not recorded for this paper

View statement
Looking for related papers…