Theorem 5 (EDPwC) — the flow relaxation has integrality gap ≥ β₁/(4c) against integral routings of congestion c − 1
ProvedEDPHardness.IntegralityGap.theorem_5_integrality_gapFor a -uniform hypergraph on vertices with hyperedges let be the edge-disjoint-paths instance of the mission: vertices for every vertex and for every hyperedge, special edges , regular edges along the hyperedges containing each in increasing order, and pairs . Here
with to base and natural.
There are absolute constants and such that for every and every integer with
there is a hypergraph as above for which
- the multicommodity flow relaxation of has a feasible fractional solution (capacity on every edge) of value , and
- every integral routing in in which every edge carries at most paths routes at most pairs.
Hence the integrality gap of the relaxation on , against integral solutions of congestion , is at least
Since has vertices, this is the EDPwC part of Theorem 5 of the paper, there written for congestion in terms of the number of vertices.
Formalization Note The theorem is stated in the explicit form Section 2 proves, in the hyperedge size (the integral congestion is ); the bound on and "sufficiently large " are the absolute constants and , chosen before and . The instance is required to be for a hypergraph with exactly hyperedges of size on vertices. The ANFwC part of Theorem 5 and its superconstant remark are not formalized.
import Mathlib import Definitions.Def_EDPHardness_IntegralityGap_FlowRelaxation import Definitions.Def_EDPHardness_IntegralityGap_GapInstance
namespace EDPHardness.IntegralityGap
theorem theorem_5_integrality_gap :
∃ α : ℝ, 0 < α ∧ ∃ N₀ : ℕ, ∀ n : ℕ, N₀ ≤ n → ∀ c : ℕ, 2 ≤ c →
(c : ℝ) ≤ α * Real.logb 2 (Real.logb 2 n) / Real.logb 2 (Real.logb 2 (Real.logb 2 n)) →
∃ H : Hyp n (numEdges n c) c,
(∃ F : FracSol (gapGraph H) (src n (numEdges n c)) (snk n (numEdges n c)),
F.value = (n : ℝ) / c) ∧
∀ R : IntRouting (gapGraph H) (src n (numEdges n c)) (snk n (numEdges n c)) (c - 1),
(R.routed.card : ℝ) ≤ 4 * (n : ℝ) / beta1 n c := by sorry
end EDPHardness.IntegralityGap
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.