Proof of Lemma 4.3, p. 349 — base case: a single-vertex (sub)tree satisfies the bound by (i)
ProvedTreewidthApprox.TreeMeasure.base_casep2o-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 , where is the set of children of ;
- whenever is the parent of .
If a vertex has no children, then the subtree rooted at consists of alone and satisfies the bound of Lemma 4.3:
This is the base case of the induction on the size of the tree in the proof of Lemma 4.3.
Formalization Note is the subtree size of the referenced rooted-tree definition (the number of descendants of , including ). The paper's base case is a tree with one vertex; here it is a leaf of a fixed tree , whose subtree is that one-vertex tree. Hypotheses (ii) and (iii) are carried for uniformity with the other steps of the proof.
Preamble
import Mathlib import Definitions.Def_HarelTarjan_Compressed_RootedTree import Definitions.Def_TreewidthApprox_TreeMeasure_Setting
Formal statement
namespace TreewidthApprox.TreeMeasure
open HarelTarjan.Compressed
theorem base_case {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) (hleaf : children T 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. 349, proof of Lemma 4.3, first paragraph (base case |V(T)| = 1)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.