AIProofWatch
← Archive
Importance: notable
VerificationAuthor claimAccessible artifact / proofFormal checking
full solutionai assisted

AI-assisted counterexample to cost-preserving unsplittable flow

The AFP development records a seven-vertex instance with fractional cost 58 but unsplittable cost at least 60, even allowing additive congestion 15.

Sources for this record

What was already known

The original rounding theorem permits additive congestion; preserving cost simultaneously was a stronger conjecture.

What changed and why it matters

Advances the stated target relative to the recorded baseline.

The AI contribution

The original announcement credits model-assisted discovery. The AFP authors explicitly disclose AI-assisted proof engineering of the finite instance.

Limitations

The formal model and its correspondence to the cost-congestion statement matter. AIProofWatch has not rebuilt Isabelle. Discovery attribution to Rybin’s model-assisted workflow is distinct from the later proof engineering.

Verification evidence

Evidence labels show what supports the claim. Importance rates its impact if correct.

Author claim

The AFP abstract states the finite cost-congestion counterexample.

Accessible artifact / proof

Isabelle session and proof documents are available.

Formal checking

AFP reports Isabelle checking; not rebuilt by AIProofWatch.

Checker: Ramos, Hulak and de Queiroz / Archive of Formal Proofs
Scope: The seven-vertex finite path-flow instance: fractional cost 58 versus unsplittable cost at least 60 with additive congestion 15.
Basis: Reported by the linked checker

Checking a formal statement does not establish that it matches the original problem.

Correction and publication history