# Verification report — OWR-14298804-012 (Peis, Pabst, Kauther, Fiorini: fare zone assignment, Oberwolfach Report 50/2024, p. 2992)

Verification date: 2026-10-15 (three independent verification runs, all AI-assisted; the third examined the final
text of the note and this package).

**Verdict.** The note answers the congestion question of the source **up to polylogarithmic factors in k**,
partly through cited theorems; every statement it makes is proved, or derived from an exactly cited
theorem. The record stays **partially solved**.
- **Settled.** With congestion k ≤ 2 the hard-cap problem is a maximum-weight simple b-matching problem,
  solvable in polynomial time on every host graph (Theorem 3.3). With k ≥ 3 it is strongly NP-hard and
  APX-hard already on stars with unit weights and unit budgets (Theorem 4.2), APX-complete for fixed k.
- **Settled given cited theorems.** For all sufficiently large k the best ratio lies between k/(C log⁴ k)
  (unless P = NP; Chan) and ek + o(k) (deterministic; Bansal–Korula–Nagarajan–Srinivasan), with
  2k + o(k) in expectation (Brubach–Sankararaman–Srinivasan–Xu) and c·k/log² k under the Unique Games
  Conjecture and NP ⊄ BPP (Austrin–Khot–Safra); (k+1)/2 + ε for unit budgets (Berman). For unbounded
  congestion there is no |E|^(1−ε)-approximation on stars unless NP = ZPP (Håstad), or unless P = NP
  (Zuckerman), and an |E|-approximation is trivial.
- **Not new mathematics.** The approximation and hardness theorems are cited, not proved here; b-matching
  (Tutte's gadget, Edmonds' algorithm; for congestion ≤ 2 the standard correspondence between 0/1 packing
  programs with at most two nonzeros per column and simple b-matching) and total unimodularity are standard. The facts stated in the source
  are the proposers'; the note gives proofs (Proposition 6.2, Theorem 4.2, Proposition 6.3).
- **Open.** The exact dependence on k (the polylogarithmic window), the best constants for small k ≥ 3, and
  the open-ended first question of the source beyond the statements of the note.

The note is unrefereed.

## Statement checked
- **Primary source.** Oberwolfach Report 50/2024, *Combinatorial Optimization* (organizers T. Rothvoss,
  L. Sanità, R. Weismantel; workshop 10–15 November 2024), Oberwolfach Reports 21(4) (2025) 2949–3000,
  doi:10.4171/OWR/2024/50; open problem "Fare Zone Assignment", presented by Britta Peis (joint work with
  Britta Peis, Philipp Pabst, Lennart Kauther and Sam Fiorini), p. 2992 (PDF page 44).
  - Read in the publisher's open PDF, downloaded on 2026-10-15 from content.ems.press (509,794 bytes,
    sha256 `50e0e930fd4253bfb0463f25c366efb86f2da607c6db7c670f70aca80dabc792`), page 44 rendered and read
    as an image; the text extraction drops the summation signs, which are visible on the page.
  - The problem: a tree G = (V, E), commodities (P_i, w_i, u_i), P_i ⊆ E a path, w_i its weight, u_i the
    maximum number of allowed cuts on P_i; maximize Σ_e y_e w_e subject to Σ_{e∈P_i} y_e ≤ u_i for all i,
    y ∈ {0,1}^E, where w_e = Σ_{i: e∈P_i} w_i. The budget is a hard constraint.
  - Facts stated without proof: polynomial when G is a path; strongly NP-hard when G is a star;
    2-approximation when all u_i are even, implying a 3-approximation when all u_i ≥ 2. (Rooted instances
    are not mentioned.)
  - Questions: what else can be said about approximation results on trees; in particular the
    approximability when the congestion (maximum number of paths sharing an edge) is bounded by k.
- **Corpus record.** ulamai/UnsolvedMath, OWR-14298804-012 (dataset version 1.6.0; upstream status
  `partially_solved`). Its statement text is garbled: the first sentences are repeated and the page header
  "Combinatorial Optimization 2993" and the title of the next open problem (Newman, 2-coloring light
  tournaments) are spliced in. The note works with the source. The record's literature note refers to the
  drop-out model of Hoefer et al. (see below).

## Readings
| Reading | Answer | Where |
|---|---|---|
| Hard cap (as in the source's program) | the model of the note | Section 1.1, Definition 2.1 |
| Drop-out model (a commodity over budget pays nothing; Hoefer et al., Definition 1) | not treated; excluded by the source itself (paths polynomial in the source, strongly NP-hard in the drop-out model) | Section 1.3 |
| Congestion = number of commodities through an edge | used | Definition 2.1 |
| Congestion = number of distinct paths through an edge | same results, by merging identical paths (summed weight, minimum budget) | Remark 2.2 |
| Weights of arbitrary sign | not treated; nonnegative weights (the source gives no sign condition) | Section 1.1 |
| Host graph other than a tree | Theorems 3.3 and 5.1 hold for any host graph and any set family | Section 2 |
| The congestion question for fixed k | answered up to polylog(k), partly by cited theorems | Theorem 1.1, Corollary 5.2 |
| The open-ended first question | only the statements of the note (incl. unbounded congestion, Corollary 4.4) | Section 1.3 |

## Results in the paper
- **Lemma 2.3 (preprocessing).** Blocked edges (on paths with budget 0) are fixed to 0, vacuous commodities
  (budget ≥ number of unblocked edges) are dropped; the reduced program has budgets 1 ≤ u_i < |P_i ∩ E'| and
  column sparsity ≤ congestion.
- **Lemmas 3.1, 3.2, Theorem 3.3.** For congestion ≤ 2: bijection with simple b-matchings of a multigraph H
  on the commodities and a dummy vertex; Tutte's gadget reduces this to maximum-weight matching (also the
  read-off from an arbitrary matching); polynomial on every host graph. Remark 3.4: congestion 1 is trivial;
  the natural relaxation is not integral at congestion 2 (triangle on a star).
- **Lemma 4.1.** Star instances Σ(H,d) (unit independent set, congestion ≤ d, all spoke weights d) and
  Σ(H,d,W) (weighted, congestion ≤ d+1); feasible ⇔ independent; OPT = d·α(H), resp. (d+1)·α_W(H); budgets 1,
  distinct paths of ≤ 2 edges; for d-regular H unit weights and congestion d.
- **Theorem 4.2.** Strongly NP-hard and APX-hard on Σ(H,3), H cubic (Alimonti–Kann); APX-complete for fixed
  k ≥ 3 with Theorem 5.1(b).
- **Theorem 4.3.** For all sufficiently large k: no k/(C log⁴ k)-approximation on stars unless P = NP (Chan,
  ECCC TR12-110, Theorem 1.4); none within c·k/log² k under UGC and NP ⊄ BPP (Austrin–Khot–Safra,
  Theorem 1.2).
- **Corollary 4.4.** Unbounded congestion: no |E|^(1−ε)-approximation on stars unless NP = ZPP (Håstad) /
  P = NP (Zuckerman); the best unblocked single edge is an |E|-approximation on every host graph.
- **Proposition 4.5 (sandwich, not an equivalence).** (a) FZ on stars with congestion ≤ k → weighted
  independent set in graphs of maximum degree ≤ k (exact correspondence); (b) unweighted independent set in
  maximum degree ≤ k and weighted independent set in maximum degree ≤ k−1 → FZ on stars with congestion ≤ k
  (Lemma 4.1); (c) the same-graph converse of (a) fails: K_{k+1} with weights (k+1,1,…,1), and K_2 with
  weights 3 and 1 for k = 1 (the example of verification run A).
- **Remark 4.6.** On Σ(K_{k+1}, k) the natural relaxation has value k(k+1)/2 and OPT = k, so its integrality gap
  is at least (k+1)/2 already on stars with congestion k.
- **Theorem 5.1, Corollary 5.2.** FZ_k is a k-column-sparse packing integer program: 8k in expectation
  (BKNS Theorem 3.3), ek + o(k) deterministic (BKNS Theorem 1.2 with the derandomization remark),
  2k + o(k) in expectation (Brubach et al. Theorem 1), (k+1)/2 + ε for unit budgets (Berman, as stated in
  BKNS §1.2 and Thiery–Ward), 1.786 for k = 3 (Thiery–Ward; a preprint of Tong–Xu, arXiv:2610.10036,
  announces 1.6908). Window Θ(k) up to polylog(k).
- **Lemma 6.1.** Matrices whose rows are vertical paths of a rooted tree are totally unimodular
  (self-contained proof).
- **Propositions 6.2, 6.3, Remark 6.4.** Paths (and instances whose paths share an end vertex, called rooted
  by Hoefer et al.) are polynomial; splitting at the highest vertex gives the ratio max u_i/⌊u_i/2⌋ (2 for
  even budgets, ≤ 3 for budgets ≥ 2) when no non-vacuous commodity has budget 1; all hardness of the note
  comes from budget-1 commodities.

## Computations (sanity checks; program and output in reproducibility/)
No proof depends on a computation. `reproducibility/check_note.py` (Python ≥ 3.10, networkx only for
maximum-weight matching with integer weights; exact arithmetic; fixed seeds; about 11 s; TOTAL failures: 0):
- Theorem 3.3 and Lemmas 3.1–3.2 against brute force on 3,000 random trees with congestion ≤ 2 and 3,000
  set systems that are not path systems (1,395,100 0/1 vectors for Lemma 3.1; 18,000 random maximal and
  partial matchings for Lemma 3.2); Remark 3.4(b); the merge remark on 600 instances.
- Lemma 4.1 for every 0/1 vector on all 2,497 pairs (H, d) with H a graph on 1–7 vertices (networkx graph
  atlas), on 6 fixed graphs, 12 random cubic graphs and 1,500 random graphs; Proposition 4.5(a) on 3,000
  random stars (congestion up to 14); Proposition 4.5(c); Remark 4.6 for k = 1..6; Corollary 4.4 on 1,500
  instances; Theorem 5.1 on 3,000 instances (1,859 with unit budgets, set-packing form for every 0/1
  vector, 11,407 candidate claws examined).
- Lemma 6.1: 314,536 exact determinants of all square submatrices of 2,000 matrices (interval, rooted,
  split, general vertical), negative control 34/500 matrices of arbitrary tree paths not TU and the star
  odd-cycle matrix with determinant 2; Proposition 6.3 on 3,000 instances (worst ratio OPT/OPT(split) = 3,
  and 2 with even budgets), with a budget-1 negative control.
- Six deliberately wrong variants of the program (copies) were each detected (375 to 162,592 failures).
- **Third verification run** (`reproducibility/independent_run_2/`, own programs written from the text before
  `check_note.py` was read; 0 failures): Lemma 3.2 for every matching of the gadget graph on 1,726 small
  instances (10,862,035 matchings), Theorem 3.3 against brute force (5,000 trees and set systems) and against a
  MILP solver (300 trees with 15–45 vertices); Lemma 4.1 on all 1,252 graphs with 1–7 vertices for three values of
  d (3,749 pairs, 931,028 vectors); Theorem 4.2 on 36 cubic graphs up to 16 vertices; Proposition 4.5(a) on 3,000
  stars; Proposition 4.5(c) by an exhaustive search over the realizations of K_{k+1} (k ≤ 4) and LP
  infeasibility (k ≤ 10); Remark 4.6 exactly (k ≤ 10); Theorem 5.1 on 3,000 trees; Lemma 6.1 exhaustively for all
  325 rooted trees with 1–7 edges (all vertical sets, Ghouila-Houri; 152,588 subdeterminants for ≤ 5 edges);
  Proposition 6.2 on 1,200 and Proposition 6.3 on 3,000 instances (ratio t attained for u = 2, 3, 4, 5, 7); seven
  wrong variants detected; and a re-run of `check_note.py` from the extracted archive (identical report).

## Independent verification runs
The results were first obtained, with proofs and three check programs, in a first written version. Three
independent verification runs, all AI-assisted, followed (2026-10-15); each re-derived the proofs and wrote its
own programs. Runs A and B examined the first written version; the note was then written with all corrections,
and its program `check_note.py` tests the final statements. The third run examined the final text of the note
and this package (below).

| Item | Run A | Run B | Writing stage |
|---|---|---|---|
| Statement against the source (hard cap, induced weights, facts, questions) | CONFIRMED (summation signs located in the PDF) | CONFIRMED | CONFIRMED (publisher's PDF, page image) |
| Lemmas 3.1, 3.2, Theorem 3.3 | CONFIRMED (3,000 set systems, 12,000 arbitrary matchings, 300 trees up to 60 vertices against a MILP solver) | CONFIRMED (2,000 trees, 666 set systems, 300 larger trees against MILP; a buggy gadget detected on 263/300) | CONFIRMED (check_note.py A1–A2) |
| Lemma 4.1, Theorem 4.2 | CONFIRMED (exhaustive on all 1,252 graphs on 1–7 vertices, 3,749 pairs (H,d)) | CONFIRMED (fixed and 15 cubic graphs, 600 random graphs, detection tests) | CONFIRMED; Theorem 4.2 restated for cubic H (unit weights) |
| Theorem 4.3 and the cited hardness theorems | CONFIRMED_WITH_FIXES (state NP ⊄ BPP) | CONFIRMED; recommended "sufficiently large k", APX-hardness only for k = 3 | CONFIRMED (AKS and Chan texts read again) |
| Theorem 5.1 and the cited algorithms | CONFIRMED_WITH_FIXES (keep "in expectation", "+ε") | CONFIRMED (verbatim in the open PDFs) | CONFIRMED (BKNS, Brubach texts read again) |
| Proposition 4.5 (stars vs bounded-degree independent set) | (a), (b) CONFIRMED; equivalence NOT JUSTIFIED (same-graph converse false, example K_2 with weights 3, 1) | CONFIRMED (600 stars) | weakened to the sandwich; example checked and generalized to K_{k+1} |
| Unbounded congestion | ADDITION REQUIRED (|E|^(1−ε) hardness) | — | added (Corollary 4.4, with Zuckerman's derandomization) |
| Propositions 6.2, 6.3 | CONFIRMED (exact TU tests, negative control) | CONFIRMED (1,800 instances, direct TU tests, negative controls) | CONFIRMED; Lemma 6.1 proved directly; Proposition 6.3 restated with blocked/vacuous commodities |
| Literature, novelty | not stale; source descriptions corrected | not stale; no prior answer found | searches repeated (arXiv, OpenAlex, zbMATH, one web search) |

No run found a false theorem, proposition or lemma, or a gap in a proof.

**Corrections required by run A**, all applied in the note:
1. Rooted instances are not among the source's facts (they come from Hoefer et al.); the star fact is listed:
   Section 1.1 lists paths, stars and the 2-/3-approximations; Section 6 says rooted instances are not in
   the source.
2. Proposition E weakened to the proved sandwich, with the one-edge example: Proposition 4.5(a)–(c), the
   sentence after it, Section 1.2.
3. The sentence that Theorems B/D "still apply with a small change" to the drop-out model was deleted; the
   note claims nothing about that model (Section 1.3).
4. arXiv:2106.10521 is the cheapest-ticket problem, arXiv:2502.08228 fare structure design by deviation from
   reference prices: "Scope and priority".
5. Edmonds–Johnson, Pulleyblank and Anstee were dropped; Tutte's gadget and Edmonds' algorithm are cited.
6. Theorem 4.3(ii) assumes the Unique Games Conjecture and NP ⊄ BPP.
7. "Randomized/in expectation" and "+ε" are kept in the abstract, Theorem 1.1, Table 1 and Theorem 5.1.
8. Merge remark: Remark 2.2.
9. Hoefer et al. contain no congestion-parameterized approximation for their problem (FZA); their f is a
   function of the number of cuts: Section 1.3.
10. Unbounded congestion: Corollary 4.4 (no |E|^(1−ε)-approximation unless NP = ZPP, Håstad; unless P = NP,
    Zuckerman; trivial |E|-approximation).
11. Status: "answered up to polylogarithmic factors; record partially solved" (abstract, Sections 1.3, 7).
12. "(planar)" for Garey–Johnson–Stockmeyer dropped (the paper is not cited).

**Recommendations of run B**, all followed: Theorem 4.3(i) for sufficiently large k, APX-hardness only for
k = 3 (Theorem 1.1(d), Theorem 4.3, Table 1); the quantitative window "given the cited theorems"
(Section 1.2, Corollary 5.2); Brubach et al. dated 2020 with online date 15 November 2019; the docstring
issue of an earlier script does not arise (the package contains only the new program).

**Changes made when the note was written, after runs A and B.**
- Theorem 4.2 is stated for cubic H, where Σ(H,3) has unit weights and congestion exactly 3.
- Proposition 6.3 is stated with blocked edges and vacuous commodities (budget-0 commodities are kept as
  split constraints with budget 0, instead of deleting blocked edges, which would destroy the path
  structure); check_note.py G1 tests this form, including vacuous budget-1 commodities.
- Lemma 6.1 replaces the citation for network matrices by a self-contained proof covering interval
  matrices, rooted instances and split matrices.
- Corollary 4.4 includes Zuckerman's theorem (abstract read on the journal's page).
- The APX-completeness of independent set in cubic graphs is cited from Alimonti–Kann; the abstract of the
  conference version (CIAC 1997) was read on the publisher's page.

### Third run: on the final text (`reproducibility/independent_run_2/`)
The third run, also AI-assisted, examined the final text of the note and the package line by line, as if nothing
had been checked, with programs of its own (Python with networkx, numpy and scipy), written before `check_note.py`
was read; verdict **CONFIRMED WITH REQUIRED FIXES**, no mathematical error, no gap.
- **Sources.** It read again p. 2992 of the Oberwolfach report (as a page image, with both summation signs),
  arXiv:2512.19493v3 (Definition 1, §§1–1.2, Proposition 2, Theorems 3, 18, 22, Corollary 6, Appendices B, C),
  BKNS (Notation, Theorems 1.2, 1.4, 3.3, both derandomization remarks, §1.2), Brubach et al. (Theorem 1), Chan
  (Theorem 1.4, footnotes, Appendix D), Austrin–Khot–Safra (§1, Definition 2.5, Theorem 4.1, §§5.2, 6), the
  abstracts of Alimonti–Kann (CIAC), Zuckerman, Thiery–Ward and Tong–Xu, and the seminar abstract of Pabst; all
  files have the sha256 values of the earlier runs. Crossref confirmed all 18 DOIs of the bibliography.
- **Proofs.** Every lemma, theorem, proposition, corollary and remark was re-derived, among them the gadget of
  Lemma 3.2 (for every matching N), the reduction of Theorem 4.2, the sandwich of Proposition 4.5 with the one-edge
  example and its generalisation to K_{k+1}, Lemma 6.1 and Proposition 6.3. No error and no gap was found.
- **Own computations.** See "Computations" above (third verification run); all checks pass, and seven wrong
  variants are detected.
- **Package.** `check_note.py` re-run from an extracted copy of the archive: report identical apart from the time
  lines (`independent_run_2/r2_package_rerun_v1.txt`).
- **Literature.** Nothing new (see below); the result is not in print as far as these searches show.

**Corrections required by the third run**, all applied in the note:
13. The abstract and §1.2 attributed all facts of the source to total unimodularity; strong NP-hardness on stars
    is Theorem 4.2. Now: total unimodularity proves the other two facts.
14. The Verification paragraph said that run A "found no false statement"; run A found no false theorem,
    proposition or lemma and no gap, but an overstated claim and wrong statements about sources. Corrected.
15. zbMATH: the eight documents for "fare zone" are not all on zone and fare design; now "none on this problem"
    ("Scope and priority").
16. Table 1, k = 3: the unit-budget ratio is 1.786 (Thiery–Ward), as in Theorem 5.1(d), not 2 + ε.
17. Credit: the reduction for congestion ≤ 2 is an instance of the standard correspondence between 0/1 packing
    programs with at most two nonzeros per column and simple b-matching (for unit budgets weighted matching, as
    noted in BKNS §1.2): Section 1.3 and "Scope and priority"; Section 3 calls the gadget a variant of Tutte's
    reduction.
18. Proposition 6.3: t ≤ 2 (not t = 2) when all non-vacuous budgets are even (t = 1 if there is none).
19. Proposition 4.5(a), proof: H has an edge ab whenever some non-vacuous commodity has the path {s_a, s_b}, so
    that H is a simple graph.
20. Remark 4.6: the integrality gap is at least (k+1)/2 (the ratio on these instances).
21. Section 1.3: Hoefer et al. outline a PTAS on paths and give exact algorithms parameterized by the congestion
    and by other parameters.
22. Record of this run: Section 7 (Verification paragraph and the folder `independent_run_2/`), this report, the
    package README. In addition, Theorem 5.1(d) mentions the preprint of Tong and Xu (1.6908 for k = 3), with a
    new reference.

## Relation to the literature, novelty and scope
- **Closest work.** Hoefer, Kauther, Pabst, Peis, Tran, *Fare Zone Assignment on Trees*, arXiv:2512.19493
  (v3, 24 April 2026; sha256 `7f7e6ef2864c30ff927146a6400133827d808628b06bf8e0e0a5430c5ef9f3d6`), read
  completely. Drop-out model (Definition 1: revenue w_i f(|P_i ∩ F|) if at most u_i cuts, else 0; f
  non-decreasing, subadditive, a function of the number of cuts). Results: O(log n) and O(log n/log log n)
  in expectation (Theorem 3, Corollary 6), exact algorithm for rooted instances (Proposition 2), APX-hard on
  stars with maximum congestion 3 (Theorem 18), strongly NP-hard on paths (Theorem 22), PTAS sketch on
  paths (Appendix C), XP/FPT on paths in congestion and budget (Appendix B). Theorem 18 is credited in the
  note as preceding Theorem 4.2. No approximation result for FZA parameterized by congestion.
- **Seminar abstract.** P. Pabst, AGCO Seminar, CMM Universidad de Chile, 24 April 2024 (one-page PDF):
  drop-out model; a variant polynomial on paths announced (joint ongoing work with Kauther, S. Müller, Peis).
- **Cited theorems read in the open versions** (sha256 identical to the versions read by the runs):
  BKNS, Theory of Computing 8 (2012) (notation, Theorems 1.2, 3.3, derandomization remark, §1.2);
  Brubach et al., arXiv:1711.02724v6 (Theorem 1, "the ratio holds in expectation"); Austrin–Khot–Safra,
  Theory of Computing 7 (2011) (Theorem 1.2, Definition 2.5, Theorem 4.1, §6); Chan, ECCC TR12-110
  (Theorem 1.4, Appendix D; the JACM version was not compared). Abstracts: Thiery–Ward (arXiv:2301.07537),
  Alimonti–Kann CIAC 1997 (publisher's page), Zuckerman (ToC page), Schöbel–Urban (arXiv:2106.10521,
  2502.08228), Tong–Xu (arXiv:2610.10036, read by the third run). All these texts were read again by the third
  run (same files by sha256). Not read: Alimonti–Kann TCS 2000, Berman 2000, Håstad 1999 (statements taken from
  the CIAC abstract, BKNS §1.2, AKS §1 and Zuckerman's abstract; the publisher's page of Håstad's paper did not
  give the text).
- **Bibliographic data** checked with Crossref (all DOIs of the bibliography).
- **Searches (2026-10-15).** arXiv API ("fare zone", "fare zones", "zone assignment": 5 hits, only
  arXiv:2512.19493 relevant; "tariff zone", "zone tariff", "fare structure": 5 hits, fare design and
  cheapest-ticket papers); OpenAlex (5 works cite the OWR volume, none on this problem; 0 cite
  arXiv:2512.19493); zbMATH ("fare zone": 8 documents, none on this problem: zone and fare design, cheapest
  tickets and paths, one unrelated paper); one web search (only arXiv:2512.19493 and unrelated pages). The
  verification runs also searched the arXiv listings of the proposers and made further web searches; the third
  run repeated the searches on the same day (arXiv API including the listings of Peis, Kauther, Pabst and
  Fiorini, OpenAlex, Crossref, zbMATH, one web search) and found nothing new: arXiv:2512.19493 is still at v3
  and no work cites it in OpenAlex. No earlier treatment of the bounded-congestion hard-cap problem
  was found; a search that finds nothing is not a proof of novelty, and no priority is claimed.
- **Scope.** The note answers the congestion question up to polylogarithmic factors in k, partly through
  cited theorems; the open-ended first question is addressed only by the statements of the note; the
  record remains partially solved.

## Public release and license
This paper, its source files, and this verification report are licensed under the Creative Commons Attribution
4.0 International License (CC BY 4.0): https://creativecommons.org/licenses/by/4.0/