Proof of Lemma 4.3, p. 350 — case p ≥ 2: at least two children give the bound at v
ProvedTreewidthApprox.TreeMeasure.case_two_or_morep2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1rooted-treetreewidth
Let be a finite rooted tree with root , let and satisfy the hypotheses (i)–(iii) of Lemma 4.3, and write . Let be a vertex with children , and suppose that every subtree rooted at a child satisfies . Then the subtree rooted at satisfies
This is the first of the two cases of the induction step in the proof of Lemma 4.3; it uses hypothesis (ii) at .
Formalization Note is the subtree size of the referenced rooted-tree definition and is the number of children of . The paper states the step at the root of the whole tree; here it is stated at an arbitrary vertex .
Preamble
import Mathlib import Definitions.Def_HarelTarjan_Compressed_RootedTree import Definitions.Def_TreewidthApprox_TreeMeasure_Setting
Formal statement
namespace TreewidthApprox.TreeMeasure
open HarelTarjan.Compressed
theorem case_two_or_more {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 : V) (hp : 2 ≤ (children T v).card)
(hIH : ∀ c ∈ children T v, (size T c : ℝ) ≤ (1 + 1 / (1 - C)) * μ c - 1) :
(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, case p ≥ 2 (second display)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.