An isolated literal’s score is independent of subinstances
ProvedStabilityDichotomies.Bijunctive.isolated_subinstance_literal_score_eq_own_shiftFor a satisfiable original instance and a variable outside every constraint scope, each literal’s score is its own shift for any graph and feasibility subinstances contained in the original instance. Thus isolated variables have no graph-step or feasibility-step changes.
Preamble
import Definitions.Def_StabilityDichotomies_Approximability_Bijunctive open scoped Classical BigOperators open StabilityDichotomies.Solvability StabilityDichotomies.Bijunctive
Formal statement
theorem StabilityDichotomies.Bijunctive.isolated_subinstance_literal_score_eq_own_shift {Γ : Language} {V : Type} [Fintype V]
(rep : TwoCNFRepresentation Γ) (I : Instance Γ V) (hI : Satisfiable I) (v : V)
(hiso : ∀ c ∈ I.constraints, ∀ k : Fin c.rel.val.arity, c.scope k ≠ v)
(G F : Instance Γ V) (hG : ∀ c ∈ G.constraints, c ∈ I.constraints)
(hF : ∀ c ∈ F.constraints, c ∈ I.constraints) (δ : Literal V → ℝ) (b : Bool) :
literalScore rep G F δ (v,b) =
((δ (v,b) : ℝ) : WithBot ℝ) := 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, sensitivity analysis.