Weighted blossom matching — verified growth event
ProvedVehicleRoutingSurvey.Routing.MatchingDispatchState.growgraph-theoryrural-postman
Consider stage of the weighted matching algorithm on compact vertices with symmetric costs. If the selected event is growth and the dispatcher enters in a valid, active state, executing its actual instruction block produces a new active, prepared search state. The execution takes at most times its charge, and the counters before and after the event satisfy the matching stage credit transition.
Preamble
import Definitions.Def_VehicleRoutingSurvey_RuralPostman1979_MatchingInterface open VehicleRoutingSurvey.Routing
Formal statement
theorem VehicleRoutingSurvey.Routing.MatchingDispatchState.grow {k i : ℕ} {cost : Fin k → Fin k → ℝ}
{original s : ArithmeticState} (before : MatchingDispatchState cost original i s)
(searching : i < k/2) (symmetric : ∀ u v, cost u v = cost v u)
(entry : s.pc = 0) (running : s.halted = false)
(active : s.nr 33 ≠ 0) (grow : matchingEventClass s = 0) :
∃ next ticks charge, BlockRuns weightedBlossomEventHandler ticks s next ∧
next.halted = false ∧ next.nr 33 ≠ 0 ∧
Nonempty (MatchingPreparedStage cost original i (matchingStageSnapshot next)) ∧
MatchingStageTransition (matchingLoopCounts k i s) charge (matchingLoopCounts k i (matchingStageSnapshot next)) ∧
ticks ≤ 1024 * (k+1) * charge := by sorrySource
J. K. Lenstra and A. H. G. Rinnooy Kan, Complexity of vehicle routing and scheduling problems (1979), Table 3, printed p. 5. https://ir.cwi.nl/pub/9658/9658D.pdf