Lemma 5.1 — a basic solution has an edge with x*_e = 1 or a vertex v ∈ U ∪ W with deg_{E*}(v) = 2
ProvedBoundedDegreeST.LowerUpper.lemma_5_1basic-solutionsiterative-roundingp2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-paperp2o-v1spanning-trees
Let be a finite simple graph, a forest on edge-disjoint from that is not a spanning tree, and a basic feasible solution of LP-MBDCT with support . Then at least one of the following holds:
- there is an edge with ;
- there is a vertex with .
This is the key lemma that makes every iteration of MBDCT Algorithm 2 progress: it either fixes an edge or removes a degree constraint.
Formalization Note The hypothesis that is not a spanning tree is implicit in the paper (Step 1 has not returned). Degree bounds are integers.
Preamble
import Definitions.Def_BoundedDegreeST_LowerUpper_LP
Formal statement
namespace BoundedDegreeST.LowerUpper
/-- Singh–Lau, Lemma 5.1, p. 668: a basic feasible solution `x*` of
LP-MBDCT(G, 𝓐, 𝓑, U, W, F) with support `E*` has an edge `e` with `x*_e = 1`,
or a vertex `v ∈ U ∪ W` with `deg_{E*}(v) = 2`. The hypothesis that `F` is not
a spanning tree is implicit in the paper (Step 1 has not returned). -/
theorem lemma_5_1 {V : Type*} [Fintype V] [DecidableEq V]
(E F : Finset (Sym2 V)) (A B : V → ℤ) (U W : Finset V) (x : Sym2 V → ℝ)
(hE : BoundedDegreeST.PlusOne.SimpleEdges E) (hF : BoundedDegreeST.PlusOne.IsForest F) (hEF : Disjoint E F)
(hbasic : Basic E A B U W F x) (hnotree : ¬ BoundedDegreeST.PlusOne.IsSpanningTree F) :
(∃ e ∈ E, x e = 1) ∨ (∃ v ∈ U ∪ W, degree (support E x) v = 2) := by sorry
end BoundedDegreeST.LowerUpper
Source
Singh, Lau, Approximating minimum bounded degree spanning trees to within one of optimal, STOC 2007, p. 668, Lemma 5.1
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.