Greedy leaf elimination gives a valid order on every encoded tree
ProvedStableMSR.Recovery.Supplement.BinaryRecovery.Regional.MenuTree.greedy_leaf_order_correctalgorithmsclusteringdynamic-programming
A longest path in each nonempty induced forest has an endpoint of degree at most one. Repeatedly removing the first eligible vertex therefore visits every vertex exactly once, with at most one later neighbor.
Preamble
import Definitions.Def_StableMSR_Recovery_Supplement_TreeLeafSchedules open StableMSR.Recovery.Supplement.BinaryRecovery.Regional open StableMSR.Recovery.Supplement.BinaryRecovery.Regional.MenuTree
Formal statement
theorem StableMSR.Recovery.Supplement.BinaryRecovery.Regional.MenuTree.greedy_leaf_order_correct (L : FactorLayout) (ht : (layoutTree L).IsTree) : GoodOrder L (leafOrder L) := by sorry
Source
Leaf elimination implementation for the bounded-treewidth dynamic program of Ravichandran and Reyzin, arXiv:2611.03547, Appendix A.6.