§2.4 ¶2 — 1/c on every canonical path is a feasible fractional solution of value n/c
ProvedEDPHardness.IntegralityGap.fractional_solutionLet and let be any hypergraph on vertices with hyperedges of size , and the EDP instance built from it, with pairs and canonical paths .
Sending units of flow on each canonical path is a feasible solution of the multicommodity flow relaxation (every edge carries at most one unit), and its value is
Precisely: there is a feasible fractional solution of value whose flow-carrying paths are canonical paths, each carrying .
This is the fractional side of the integrality gap: the LP optimum of is at least for every .
Formalization Note A flow-carrying path is identified as canonical by its vertex sequence. The statement holds for every (no randomness is needed); a vertex in no hyperedge has the canonical path by the convention of the definitions.
import Mathlib import Definitions.Def_EDPHardness_IntegralityGap_FlowRelaxation import Definitions.Def_EDPHardness_IntegralityGap_GapInstance
namespace EDPHardness.IntegralityGap
theorem fractional_solution (n c : ℕ) (hc : 2 ≤ c) (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 ∧
∀ v, ∀ P ∈ F.paths v, P.support = canonicalSupport H v ∧ F.f v P = 1 / (c : ℝ) := by sorry
end EDPHardness.IntegralityGap
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.