Polynomial-accuracy LOCAL matching booster with physical round accounting
ProvedFasterDistributedMatching.ApproximateMatching.fmu_local_boosterFix a constant approximation fraction . There are positive integers , depending only on , that implement the Fischer--Mitrović--Uitto matching booster in the synchronous deterministic LOCAL model.
Fix a polynomial identifier convention and a protocol that, on every bounded finite simple graph with identifiers below , reports an actual matching of size at least times the optimum. Then there is one protocol , fixed before network inputs and the integer accuracy parameter , that for every reports a matching satisfying
Write for the round count of with common bounds . Protocol satisfies
The input to consists of the common bounds and , the processor's own identifier, and its neighbor identifiers; its identifiers need only be below . All simulated communication is charged in physical rounds, and all private tapes are ignored. This separates the booster from the construction and time analysis of a constant-approximation oracle.
Formalization Note This is the LOCAL specialization of the framework, with reciprocal integer accuracy, one polynomial padding large enough for all auxiliary graph sizes, degrees, routes and processing times, and a common padded bound used for every oracle invocation. Specializing the source parameter to gives the stated approximation factor.
import Mathlib import Definitions.Def_FasterDistributedMatching_ApproximateMatching_Local open FasterDistributedMatching.ApproximateMatching
theorem FasterDistributedMatching.ApproximateMatching.fmu_local_booster :
∀ c : ℝ, 0 < c → c ≤ 1 →
∃ p C : ℕ, 1 ≤ p ∧ 0 < C ∧
∀ (b : ℕ) (A : Deterministic Bounds (Finset ℕ) (Option ℕ)),
(∀ (N : ℕ) (G : SimpleGraph (Fin N)) (k : Bounds),
boundedGraph G k.n k.degree →
∀ ids : Fin N → ℕ, Identifiers k.n (b+4) ids →
∃ M : SimpleGraph (Fin N),
ReportsMatching G ids (execute A G k ids (neighborIDs G ids)) M ∧
c*(optimum G:ℝ) ≤ (matchingSize M:ℝ)) →
∃ B : Deterministic (Bounds × ℕ) (Finset ℕ) (Option ℕ),
(∀ (k : Bounds) (q : ℕ), 2 ≤ q →
B.program.rounds (k,q) ≤ C*(q+1)^p*
(A.program.rounds ⟨(k.n+1)*(q+1)^p,(k.degree+1)*(q+1)^p⟩+(q+1)^p)) ∧
∀ (N : ℕ) (G : SimpleGraph (Fin N)) (k : Bounds) (q : ℕ),
2 ≤ q → boundedGraph G k.n k.degree →
∀ ids : Fin N → ℕ, Identifiers k.n (b+1) ids →
∃ M : SimpleGraph (Fin N),
ReportsMatching G ids (execute B G (k,q) ids (neighborIDs G ids)) M ∧
(optimum G:ℝ) ≤ (1+1/(q:ℝ))*(matchingSize M:ℝ) := by sorry