A surviving shortest path preserves its distance after arc deletion
ProvedStabilityDichotomies.Bijunctive.shortest_distance_preserved_if_path_survivesIf an implication graph loses arcs but retains a shortest walk of length from a root to a target, then their new shortest-path distance remains .
Preamble
import Definitions.Def_StabilityDichotomies_Approximability_Bijunctive open scoped Classical BigOperators open StabilityDichotomies.Solvability StabilityDichotomies.Bijunctive
Formal statement
theorem StabilityDichotomies.Bijunctive.shortest_distance_preserved_if_path_survives {Γ : Language} {V : Type}
(rep : TwoCNFRepresentation Γ) (G G' : Instance Γ V)
(hsub : ∀ a b, implicationArc rep G' a b → implicationArc rep G a b)
(root target : Literal V) (n : ℕ)
(hd : implicationDistance rep G root target = some n)
(hw : WalkLength (implicationArc rep G') n root target) :
implicationDistance rep G' root target = some n := by
sorrySource
Wang and Yoshida, Stability Dichotomies for Boolean CSPs, STOC 2027, https://github.com/sigact-stoc/stoc2027/releases/download/papers-1/535.pdf, proof of Theorem 4.9, graph deletion step.