跳到正文
研踪PaperTrail
← 研踪 PaperTrail

arXiv:2611.20475 · v1

Rounded Potentials Certify Exact Maximum Flow

首次提交 2026-11-16 11:39
版本更新 2026-11-16 11:39
雷达观测 2026-11-17 13:07
arXiv ↗PDF ↗

摘要

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

AI 论文解读

基于摘要 · 非全文审阅

此版本尚未生成 AI 解读。解读由后台任务生成并按论文版本保存,登录后共享已有结果。

版本差异

目前只收录了一个版本。收录下一版后,可以对照标题、作者、分类和摘要。

观测到的版本

相邻记录可能跳过中间版本;首次发现 v2 及以上也会标为版本更新。

v1 · 2026-11-16 11:39 · 最新观测版本

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

查看此版本解读 →查看此版本原文 ↗