Β§2.4 β |π«β| β€ n/Ξ²β: if β°β fails, at most n/Ξ²β pairs are routed on their canonical paths
ProvedEDPHardness.IntegralityGap.canonical_paths_boundedge-disjoint-pathsintegrality-gapp2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-paperp2o-v1
Let , assume , and let be a hypergraph on vertices with hyperedges of size for which the event does not occur (every set of vertices contains a hyperedge). Consider any integral routing in with congestion at most , and let be the set of routed pairs whose path is their canonical path. Then
Otherwise some hyperedge would have all of its vertices routed canonically, and its special edge would carry paths.
Formalization Note "Routed on its canonical path" means that the routing path has the vertex sequence of .
Preamble
import Mathlib import Definitions.Def_EDPHardness_IntegralityGap_FlowRelaxation import Definitions.Def_EDPHardness_IntegralityGap_GapInstance
Formal statement
namespace EDPHardness.IntegralityGap
theorem canonical_paths_bound (n c : β) (hc : 2 β€ c) (hΞ²β : 0 < beta1 n c)
(H : Hyp n (numEdges n c) c) (hEβ : Β¬ E1 n c H)
(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)).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 |P1|)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.