Lemma 5.7 (used in the proof of Theorem 1.3) — branching budget and correctness
OpenFasterExactColoring.ThreeColor.Supplement.branching_reductionsexact-algorithmsgraph-theoryp2o-batch-stoc27sp2o-gran-per-chapterp2o-plan-paperp2o-v1
Fix and nonnegative measure weights with , for , satisfying every linear and branching constraint of Appendix D. There are one deterministic finite program and uniform constants such that for each valid nonterminal restricted instance it generates a finite list of valid restricted instances. All four requirements hold:
The execution outputs exactly the encoded children, and each child retains the same graph . An empty list is permitted only when the equivalence establishes that is unsatisfiable. This is this paper's restatement of the cited branching lemma, including budget, both correctness directions, strict decrease and polynomial overhead per child.
Differences from the source:
- encoding: branching reductions generate the subinstances with polynomial overhead per subinstance → one deterministic finite program outputs the complete list of changed I,S sets on the same graph, with cost poly(inputCost)*(t+1); reason: the list encoding charges generation and output, also handling an empty rejecting branch; all four source guarantees remain conclusions
Preamble
import Mathlib import Definitions.Def_FasterExactColoring_ThreeColor_Supplement_Measure import Definitions.Def_FasterExactColoring_ThreeColor_Supplement_TerminalBounds set_option autoImplicit false
Formal statement
namespace FasterExactColoring.ThreeColor.Supplement
theorem branching_reductions (r : ℝ) (w : Weights) (hr : 1 < r) (hw : appendixD r w) :
∃ (A : Program) (C : ℝ) (d : ℕ), 0 < C ∧ deterministic A ∧
∀ (n : ℕ) (P : Restricted n), P.valid → ¬ P.terminal →
∃ L : List (Finset (Fin n) × Finset (Fin n)),
(∀ IS ∈ L, (child P IS).valid ∧ (child P IS).U.card < P.U.card) ∧
((L.map (fun IS => r^(measure w (child P IS)))).sum ≤ r^(measure w P)) ∧
(P.colorable ↔ ∃ IS ∈ L, (child P IS).colorable) ∧
runWithin A P.code (polynomial C d P.code * (L.length+1 : ℕ))
(fun y => y = childrenCode L) := by sorry
end FasterExactColoring.ThreeColor.Supplement
Source
Ryosuke Yamano, Tetsuo Shibuya, STOC 2027 submission #727 (October 2026), Lemma 5.7, p. 15 (PDF p. 17)