AI-Assisted Bounds and Decompositions for Cost-Preserving Unsplittable Flows

In a three-paper series culminating on August 13, 2026, Sergey Nikolenko reports new lower bounds and structural upper bounds for cost-preserving single-source unsplittable flow. The problem asks whether a feasible fractional flow can be rounded to one path per terminal while preserving cost and increasing every arc load by at most $C d_{\max}$. Following the earlier disproof of the conjectured value $C=1$, the series raises the general lower-bound record to approximately $1.28260069$, proves a planar lower bound of approximately $1.17353532$, and gives the first finite constants for several unbounded structural classes.

The third paper reframes cost preservation through exact-mean probability distributions over integral routings: when the mean equals the fractional flow, every linear cost is preserved automatically. It obtains radius $2d_{\max}$ for route-difference systems of row arity at most three, identifies exact local envelopes at arities three and four, and reduces existence of a universal constant to finiteness in a single factor-two demand band, with at most a factor-two loss. Nikolenko states that GPT 5.6 Sol, Claude Fable 5, and Claude Opus 5 contributed proofs, failed approaches, adversarial reviews, and verification code; he describes substantial human involvement and says he personally verified and edited the work.

The repository supplies all three manuscripts, exact rational or symbolic certificates, and independently written verifiers that reconstruct instances from raw arc lists and re-derive the finite numerical claims. These results do not settle whether a universal constant exists, and the class-specific ceilings in the second paper are explicitly not universal upper bounds.