One polynomial-time RAM algorithm for the flow-cut alternative
ProvedLax455465Proofs.RamProductAlgorithm.exists_polynomial_time_flow_cutalgorithmscomputational-complexitygraph-theory
There are a single polynomial-time word-RAM algorithm and a positive universal constant such that every valid rational product-demand network with at least two positive-demand vertices has a joint flow-cut certificate:
The statement includes both edge models and total resource bounds on arbitrary input words.
Preamble
import Definitions.Def_EdgeSublinearMWIS_Main_NativeSchemeInterfaces
Formal statement
theorem Lax455465Proofs.RamProductAlgorithm.exists_polynomial_time_flow_cut : ∃ (solve : List ℕ → List ℕ) (C : ℝ),
Lax759944.RamPolytime.RamPolytime solve ∧
0 < C ∧
∀ (kind : Lax455465.ProductNetwork.EdgeKind) (n : ℕ) (I : Lax455465.RationalEncoding.RationalInstance n),
(kind = Lax455465.ProductNetwork.EdgeKind.undirected → I.network.IsUndirected) →
2 ≤ Lax455465.ProductNetwork.supportCount I.weights →
∃ (certificate : Lax455465.FlowCutCertificate.Certificate n),
solve (Lax455465.RationalEncoding.encodeInput kind I) =
Lax455465.FlowCutCertificate.encodeCertificate certificate ∧
Lax455465.FlowCutCertificate.IsValid kind I C certificate := by sorrySource