Greedy leaf elimination runs in polynomial bit time
ProvedStableMSR.Recovery.Supplement.BinaryRecovery.Regional.MenuTree.greedy_leaf_order_bit_programalgorithmsclusteringdynamic-programming
Compute each active list by at most n filters on the original n vertices and select the first low-degree vertex. Filtering can only decrease the encoded list length.
Preamble
import Definitions.Def_StableMSR_Recovery_Supplement_TreeLeafSchedules import Definitions.Def_QuantumMaxCutFiniteNumericRuntime open StableMSR.Recovery.Supplement.BinaryRecovery.Regional open StableMSR.Recovery.Supplement.BinaryRecovery.Regional.MenuTree open OAI.MetricKMedian.Binary.Automatic
Formal statement
theorem StableMSR.Recovery.Supplement.BinaryRecovery.Regional.MenuTree.greedy_leaf_order_bit_program : Poly leafOrder := by sorry
Source
Leaf elimination implementation for the bounded-treewidth dynamic program of Ravichandran and Reyzin, arXiv:2611.03547, Appendix A.6.