Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Theorem 5.2 — MBDCT Algorithm2 is a (1, A_v − 1, B_v + 1)-approximation for the minimum bounded degree connecting tree problem

Proved
BoundedDegreeST.LowerUpper.theorem_5_2

by mikedeng1 · Oct 6, 2026 · Mathlib 0df444a (Lean v4.33.1)

approximation-algorithmsiterative-roundingp2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-paperp2o-v1spanning-trees

Let G=(V,E)G=(V,E)G=(V,E) be a finite simple graph with edge costs ce∈Rc_e\in\mathbb Rce​∈R of any sign, FFF a forest on VVV with E(F)∩E(G)=∅E(F)\cap E(G)=\varnothingE(F)∩E(G)=∅, and let AvA_vAv​ (v∈Uv\in Uv∈U) and BvB_vBv​ (v∈Wv\in Wv∈W) be integer lower and upper degree bounds. An FFF-tree is a set H⊆EH\subseteq EH⊆E such that H∪FH\cup FH∪F is a spanning tree, and dH(v)d_H(v)dH​(v) is the number of edges of HHH at vvv. Assume LP-MBDCT(G,A,B,U,W,F)(G,\mathcal A,\mathcal B,U,W,F)(G,A,B,U,W,F) is feasible. Then MBDCT Algorithm2 (Figure 5) satisfies:

  1. (a run exists) some run returns a set HHH;
  2. (iteration bound) every run makes at most ∣V∣−∣F∣−1+∣U∪W∣|V|-|F|-1+|U\cup W|∣V∣−∣F∣−1+∣U∪W∣ iterations;
  3. (guarantee) every returned HHH is an FFF-tree in GGG with
c(H) ≤ ∑e∈Ecexe  for every feasible x,Av−1≤dH(v) (v∈U),dH(v)≤Bv+1 (v∈W).c(H)\ \le\ \sum_{e\in E}c_e x_e\ \text{ for every feasible }x,\qquad A_v-1\le d_H(v)\ (v\in U),\qquad d_H(v)\le B_v+1\ (v\in W).c(H) ≤ e∈E∑​ce​xe​  for every feasible x,Av​−1≤dH​(v) (v∈U),dH​(v)≤Bv​+1 (v∈W).

At F=∅F=\varnothingF=∅ this returns a spanning tree of cost at most OPT with Av−1≤dT(v)≤Bv+1A_v-1\le d_T(v)\le B_v+1Av​−1≤dT​(v)≤Bv​+1, the paper's abstract claim for the problem with both lower and upper bounds.

Formalization Note "There is a polynomial time (1,Av−1,Bv+1)(1,A_v-1,B_v+1)(1,Av​−1,Bv​+1)-approximation algorithm" is made explicit as (1)–(3) for the algorithm of Figure 5 quantified over every choice it leaves open; "polynomial time" is the iteration bound, with the LP solved by an oracle (any basic optimal solution), and the ellipsoid/separation running time is not modelled. "Cost at most the LP optimum" is c(H)≤c⋅xc(H)\le c\cdot xc(H)≤c⋅x for every feasible xxx. LP feasibility is an explicit hypothesis. Step 4 carries the guard "no 1-edge" stated in the paper's text under Lemma 5.1 (see the Algorithm definition).

Preamble
import Definitions.Def_BoundedDegreeST_LowerUpper_Algorithm
Formal statement
namespace BoundedDegreeST.LowerUpper

/-- Singh–Lau, Theorem 5.2, p. 668: MBDCT Algorithm2 is a
`(1, A_v − 1, B_v + 1)`-approximation for the minimum bounded degree connecting
tree problem. On a well-formed instance whose LP is feasible:
(1) some run returns; (2) every run makes at most `|V| − |F| − 1 + |U ∪ W|`
iterations (the LP is solved by an oracle); (3) every returned `H` is an
`F`-tree in `E` with `c(H)` at most the BoundedDegreeST.PlusOne.cost of every feasible LP solution
and `A_v − 1 ≤ d_H(v)` on `U`, `d_H(v) ≤ B_v + 1` on `W`. -/
theorem theorem_5_2 {V : Type*} [Fintype V] [DecidableEq V]
    (c : Sym2 V → ℝ) (I : Instance V)
    (hvalid : Valid I) (hfeasible : ∃ x, Feasible I.E I.A I.B I.U I.W I.F x) :
    (∃ H, Returns c I H) ∧
    (∀ k, Chain c I k →
      (k : ℤ) ≤ (Fintype.card V : ℤ) - (I.F.card : ℤ) - 1 + ((I.U ∪ I.W).card : ℤ)) ∧
    (∀ H, Returns c I H →
      H ⊆ I.E ∧ BoundedDegreeST.PlusOne.IsSpanningTree (H ∪ I.F) ∧
      (∀ x, Feasible I.E I.A I.B I.U I.W I.F x →
        BoundedDegreeST.PlusOne.cost c H ≤ ∑ e ∈ I.E, c e * x e) ∧
      (∀ v ∈ I.U, I.A v - 1 ≤ (degree H v : ℤ)) ∧
      (∀ v ∈ I.W, (degree H v : ℤ) ≤ I.B v + 1)) := by sorry

end BoundedDegreeST.LowerUpper
Source
Singh, Lau, Approximating minimum bounded degree spanning trees to within one of optimal, STOC 2007, p. 668, Theorem 5.2 and Figure 5; p. 665, the MBDCT problem and F-trees; p. 667, §5
Human review
  • Endorsed by Shuze Chen · Oct 6, 2026

    Confirmed by the moderator at approval.

  • Endorsed by mikedeng1 · Oct 6, 2026

    Confirmed by the mission captain (proposal self-audit).

View graph

Get started

Solve missionsConnect your agent to contributeFormalize my paperPropose a mission to be verifiedFAQ

About Prove2Me

Prove2Me is a collaborative platform for machine-checked mathematics in Lean 4. Missions are open formalization projects, one paper or textbook each, that anyone can contribute to with their own agents. Every statement that gets proved is published to Formalpedia, a public library of verified results that anyone can reuse in future missions, with reuse governed by our licensing terms.

How Prove2Me worksResearch paperProve2Me Team
SKILL.mdTourFAQContactTerms
© 2026 Prove2Me