Lemma 4.3 — a rooted tree with a measure μ ≥ 1, superadditive over children and shrinking by C < 1 to each child, has at most (1 + 1/(1−C))μ(r) − 1 vertices
ProvedTreewidthApprox.TreeMeasure.lemma_4_3Let be a finite rooted tree with root . Suppose is a measure on its vertices and is a real constant with such that:
- for every ;
- for every vertex with children (possibly ), ;
- for every two vertices such that is the parent of , .
Then
In the paper this bounds the number of nodes of the partial tree decomposition built by the algorithm FindPartialTD, applied with ; it turns a measure that is superadditive over children and decays geometrically along every root-to-leaf path into a linear bound on the size of the tree.
Formalization Note The rooted tree is the referenced HarelTarjan.Compressed.RootedTree: a finite vertex type with a root and a parent map in which every vertex reaches the root, with the convention ; is the cardinality of . " is a child of " means and . The paper's "there exists a constant " is a given constant with hypotheses and , because the conclusion is stated with that ; the hypothesis also keeps the real division from being the Lean default .
import Mathlib import Definitions.Def_HarelTarjan_Compressed_RootedTree import Definitions.Def_TreewidthApprox_TreeMeasure_Setting
namespace TreewidthApprox.TreeMeasure
open HarelTarjan.Compressed
theorem lemma_4_3 {V : Type*} [Fintype V] [DecidableEq V] (T : RootedTree V)
(μ : V → ℝ) (C : ℝ) (hC₀ : 0 < C) (hC₁ : C < 1)
(h₁ : ∀ v, 1 ≤ μ v)
(h₂ : ∀ v, ∑ c ∈ children T v, μ c ≤ μ v)
(h₃ : ∀ v c, IsChild T v c → μ c ≤ C * μ v) :
(Fintype.card V : ℝ) ≤ (1 + 1 / (1 - C)) * μ T.root - 1 := by sorry
end TreewidthApprox.TreeMeasure
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.