§2.4 — |𝒫₂| ≤ n/β₁: at most n/β₁ pairs use non-canonical paths of length ≥ g
ProvedEDPHardness.IntegralityGap.long_paths_boundedge-disjoint-pathsintegrality-gapp2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-paperp2o-v1
Let , assume and , let , and let be any hypergraph on vertices with hyperedges of size . In every integral routing in with congestion at most , the set of pairs routed on a non-canonical path with at least edges satisfies
The reason is capacity: has at most edges, so the total length of all routing paths is at most , and .
Formalization Note Length is the number of edges of on the path. The paper's count "at most edges" uses hyperedges and large; the hypothesis makes it hold (it holds in the regime of Theorem 5).
Preamble
import Mathlib import Definitions.Def_EDPHardness_IntegralityGap_FlowRelaxation import Definitions.Def_EDPHardness_IntegralityGap_GapInstance
Formal statement
namespace EDPHardness.IntegralityGap
theorem long_paths_bound (n c : ℕ) (hc : 2 ≤ c) (hβ₁ : 0 < beta1 n c) (hβ₂ : 1 ≤ beta2 n c)
(H : Hyp n (numEdges n c) c)
(R : IntRouting (gapGraph H) (src n (numEdges n c)) (snk n (numEdges n c)) (c - 1)) :
((Finset.univ.filter
(fun v : R.routed => (R.path v).support ≠ canonicalSupport H v ∧
gParam n c ≤ (R.path v).length)).card : ℝ)
≤ (n : ℝ) / beta1 n c := by sorry
end EDPHardness.IntegralityGap
Source
Andrews, Chuzhoy, Guruswami, Khanna, Talwar, Zhang, Inapproximability of Edge-Disjoint Paths and Low Congestion Routing on Undirected Graphs, Combinatorica 30 (2010), p. 495, Section 2.4, Gap Analysis for EDPwC (bound on |P2|)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.