Theorem 1.2 — cost at most optimum, degrees at most B + 1
ProvedBoundedDegreeST.PlusOne.theorem_1_2For a finite simple undirected graph , arbitrary real edge costs , and integer upper bounds , suppose the bounded-degree spanning-tree LP is feasible. The Figure 4 algorithm started with no selected edges and degree constraints at every vertex has a terminating run, every run takes at most iterations, and every returned spanning tree satisfies
In particular, for every spanning tree satisfying all the original degree bounds, hence is at most the original optimum. This is the paper's approximation guarantee.
Formalization Note The goal uses LP-MBDCT with and , which gives LP (1)–(5). The iteration bound represents the combinatorial part of polynomial time; LP solver complexity is outside the formal statement. Run existence prevents an empty return relation from making the guarantee vacuous.
import Definitions.Def_BoundedDegreeST_PlusOne_Algorithm
namespace BoundedDegreeST.PlusOne
/-- Singh–Lau, Theorem 1.2, p. 661, via Figure 4 at `F = ∅`, `W = V`. -/
theorem theorem_1_2 {V : Type*} [Fintype V] [DecidableEq V]
(E : Finset (Sym2 V)) (c : Sym2 V → ℝ) (B : V → ℤ)
(hsimple : SimpleEdges E)
(hfeasible : ∃ x, Feasible E B Finset.univ ∅ x) :
(∃ T, Returns c (initial E B) T) ∧
(∀ k, Chain c (initial E B) k →
(k : ℤ) ≤ 2 * (Fintype.card V : ℤ) - 1) ∧
(∀ T, Returns c (initial E B) T →
T ⊆ E ∧ IsSpanningTree T ∧
(∀ v : V, (degree T v : ℤ) ≤ B v + 1) ∧
(∀ x, Feasible E B Finset.univ ∅ x →
cost c T ≤ ∑ e ∈ E, c e * x e) ∧
(∀ T₀ : Finset (Sym2 V), T₀ ⊆ E → IsSpanningTree T₀ →
(∀ v : V, (degree T₀ v : ℤ) ≤ B v) →
cost c T ≤ cost c T₀)) := by sorry
end BoundedDegreeST.PlusOne
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.