Proved
Planar cost theorem with doubled allowance ↗
Planar instances with upper and lower deviation at most 2 d_max.
Source dated Aug 4, 2023 · Observed Oct 13, 2026
Theorem · version 1
Preserving cost with twice the allowance in planar graphs
Statement
For a planar single-source unsplittable-flow instance and nonnegative rational arc costs, there exists an unsplittable routing P with x(a) − 2 d_max ≤ load_P(a) ≤ x(a) + 2 d_max on every arc and total cost no larger than the fractional cost.
Assumptions
- The planar acyclic instance model of the cited paper.
- Rational nonnegative demands and arc costs.
Scope
Traub–Vargas Koch–Zenklusen’s planar theorem has a larger allowance and therefore survives the counterexample.
Evidence
Source reports
Connections
In this problem · publication v9 · Selected context
Cost-preserving unsplittable flow →
Different statement · related variant · Proved
Relationship not independently reviewed. This concerns its use in this problem.
Sources
Single-Source Unsplittable Flows in Planar Graphs →
- Definition 1.1, Theorem 1.2, Conjecture 1.3 and Theorem 1.8 → · Original passage ↗
Recorded wording
The paper states the original congestion theorem, Goemans’ cost-enhanced conjecture and a planar theorem with twice the largest-demand allowance.
paraphrase · OpenMath supplies its own mathematical paraphrases and links; proof text is not republished.
Vera Traub · Laura Vargas Koch · Rico Zenklusen · Preprint · Publication date Aug 4, 2023
Revision & attribution
Source revision: 2023-08-04. Observed Oct 13, 2026.
No specific AI contribution is attributed by this source record.
History
Statement versions
Statement versions and problem publication versions are separate. A new publication can update context or sources while retaining the same statement.
Assessment history · 1
Assessments retained in these publication records. Earlier statement versions retain their own source histories.
Proved
Planar cost theorem with doubled allowance ↗
Planar instances with upper and lower deviation at most 2 d_max.
Source dated Aug 4, 2023 · Observed Oct 13, 2026 · Source passage →
Record details
- Claim ID
- claim-flow-planar-two-demand-allowance
- Statement version
- 1
- SHA-256
- a4a2b568e49e280305ee1cf44b20d767340c60badf3b767c2eac8e86e73e844c