← 研踪 PaperTrailarXiv:2611.20475 · v1
Rounded Potentials Certify Exact Maximum Flow
首次提交 2026-11-16 11:39
版本更新 2026-11-16 11:39
雷达观测 2026-11-17 13:07
摘要
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 terminal pairs for which every maximum flow uses edges. Yet we show that one short number per vertex suffices for both cut and flow: vertex potentials, each rounded to bits, certify the exact maximum -flow value in any directed graph with integer capacities at most . 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. total cost (help plus space) for the maximum -flow value, optimal up to logarithmic factors, answering a question of Thaler (ICALP 2016) on whether is possible. - Broadcast proof-labeling. -bit labels certifying a maximum -flow value of in directed and undirected graphs with arbitrary capacities, optimal for , settling that regime of a question of Korman, Kutten, and Peleg (Distributed Computing 2010). - Merlin-Arthur verification. time and proof length for directed All-Pairs Max-Flow, improving on previous verification times of for general capacities and for unit capacities, and answering a question of Akmal (TheoretiCS 2024). - Nondeterministic algorithms. time for directed All-Pairs Max-Flow, or if : the first subquartic bound for general edge capacities, answering a question of Trabelsi (SODA 2025).
观测到的版本
相邻记录可能跳过中间版本;首次发现 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 terminal pairs for which every maximum flow uses edges. Yet we show that one short number per vertex suffices for both cut and flow: vertex potentials, each rounded to bits, certify the exact maximum -flow value in any directed graph with integer capacities at most . 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. total cost (help plus space) for the maximum -flow value, optimal up to logarithmic factors, answering a question of Thaler (ICALP 2016) on whether is possible. - Broadcast proof-labeling. -bit labels certifying a maximum -flow value of in directed and undirected graphs with arbitrary capacities, optimal for , settling that regime of a question of Korman, Kutten, and Peleg (Distributed Computing 2010). - Merlin-Arthur verification. time and proof length for directed All-Pairs Max-Flow, improving on previous verification times of for general capacities and for unit capacities, and answering a question of Akmal (TheoretiCS 2024). - Nondeterministic algorithms. time for directed All-Pairs Max-Flow, or if : the first subquartic bound for general edge capacities, answering a question of Trabelsi (SODA 2025).
查看此版本解读 →查看此版本原文 ↗