Lemma 4.3 — laminar basis for a basic LP solution
ProvedBoundedDegreeST.PlusOne.lemma_4_3iterative-roundinglinear-programmingp2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-paperp2o-v1spanning-trees
Let be a basic feasible solution of LP-MBDCT on a well-formed graph and forest before the terminal step, and let be its support. There are a nonempty laminar family of nonempty unions of forest components and a set such that the tight equations
uniquely determine on . Their characteristic vectors are linearly independent and .
This identifies the tight rows used by the token-counting argument.
Formalization Note The linear system, uniqueness and independence are all on the support variables. The nonterminal condition excludes the zero-variable terminal LP.
Preamble
import Definitions.Def_BoundedDegreeST_PlusOne_Algorithm
Formal statement
namespace BoundedDegreeST.PlusOne
/-- Singh–Lau, Lemma 4.3, p. 666. -/
theorem lemma_4_3 {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) :
∃ (L : Finset (Finset V)) (T : Finset V),
DefinesBasis I.E I.B I.W I.F x L T := 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.3
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.