Lemma 4.1 — a 1-edge or a removable degree constraint
ProvedBoundedDegreeST.PlusOne.lemma_4_1iterative-roundinglinear-programmingp2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-paperp2o-v1spanning-trees
Let be a basic feasible solution of LP-MBDCT in a well-formed, nonterminal instance, and let be its support. Then at least one of the following holds:
This guarantees that an iteration of the rounding algorithm can change its state.
Formalization Note The forest is required not to be a spanning tree, since Figure 4 would already have returned at Step 1.
Preamble
import Definitions.Def_BoundedDegreeST_PlusOne_Algorithm
Formal statement
namespace BoundedDegreeST.PlusOne
/-- Singh–Lau, Lemma 4.1, p. 666. -/
theorem lemma_4_1 {V : Type*} [Fintype V] [DecidableEq V]
(I : Instance V) (x : Sym2 V → ℝ)
(hvalid : Valid I) (hbasic : Basic I.E I.B I.W I.F x)
(hnotree : ¬ IsSpanningTree I.F) :
(∃ e ∈ I.E, x e = 1) ∨
(∃ w ∈ I.W, (degree (support I.E x) w : ℤ) ≤ I.B w + 1) := by sorry
end BoundedDegreeST.PlusOne
Source
Singh, Lau, Approximating minimum bounded degree spanning trees to within one of optimal, STOC 2007, p. 666, Lemma 4.1
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.