Proof of Lemma 4.3, p. 350 — case p = 1: one child gives the bound at v
ProvedTreewidthApprox.TreeMeasure.case_onep2o-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 exactly one child , and suppose that . Then
This is the second of the two cases of the induction step in the proof of Lemma 4.3; it uses hypothesis (iii) on the edge from to and hypothesis (i) at .
Formalization Note is the subtree size of the referenced rooted-tree definition. The paper states the step at the root of the whole tree; here it is stated at an arbitrary vertex . The induction hypothesis is stated for every child of , of which there is exactly one.
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_one {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 : (children T v).card = 1)
(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 = 1 (third display)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.