Leaf elimination returns optimal legal labelings for every total
ProvedStableMSR.Recovery.Supplement.BinaryRecovery.Regional.MenuTree.leaf_message_semanticsalgorithmsclusteringdynamic-programming
For a supplied elimination order of width one, merging only needs agreement between a leaf state and its one later neighbor. After compression, full witnesses still attain every attainable total with minimum rational weight. The extra empty root handles isolated vertices.
Preamble
import Definitions.Def_StableMSR_Recovery_Supplement_TreeMenuMessages open StableMSR.Recovery.Supplement.BinaryRecovery.Regional open StableMSR.Recovery.Supplement.BinaryRecovery.Regional.MenuTree
Formal statement
theorem StableMSR.Recovery.Supplement.BinaryRecovery.Regional.MenuTree.leaf_message_semantics (I : Instance) (xs : Block) (hx : GoodOrder I.1 xs) : Optima I (optimize I xs) := by sorry
Source
Leaf elimination implementation for the bounded-treewidth dynamic program of Ravichandran and Reyzin, arXiv:2611.03547, Appendix A.6.