Proof of Lemma 4.3, p. 350 — the bound holds for the subtree rooted at every vertex
ProvedTreewidthApprox.TreeMeasure.lemma_4_3_subtreep2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1rooted-treetreewidth
Let be a finite rooted tree with root , and let and satisfy the hypotheses of Lemma 4.3:
- for every vertex ;
- for every vertex ;
- whenever is the parent of .
Then for every vertex the subtree rooted at satisfies
The proof of Lemma 4.3 applies the lemma to the subtrees rooted at the children of the root (the "induction hypothesis"); this is that statement for all subtrees at once. At it is Lemma 4.3 itself.
Formalization Note is the subtree size of the referenced rooted-tree definition (the descendants of , including ).
Preamble
import Mathlib import Definitions.Def_HarelTarjan_Compressed_RootedTree import Definitions.Def_TreewidthApprox_TreeMeasure_Setting
Formal statement
namespace TreewidthApprox.TreeMeasure
open HarelTarjan.Compressed
theorem lemma_4_3_subtree {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) :
∀ v, (size T v : ℝ) ≤ (1 + 1 / (1 - C)) * μ v - 1 := by sorry
end TreewidthApprox.TreeMeasure
Source
Bodlaender, Drange, Dregi, Fomin, Lokshtanov and Pilipczuk, A c^k n 5-approximation algorithm for treewidth, SIAM J. Comput. 45(2) (2016), p. 350, proof of Lemma 4.3 (induction hypothesis applied to T_1, …, T_p)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.