Proof of Lemma 6.5, pp. 369–370 — the four inequalities for L ∩ Aᵢ and R ∩ Aᵢ
ProvedTreewidthApprox.Pushed.four_inequalitiesbalanced-separatorgraph-separationp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1treewidth
Let be a finite graph and an integer. Let be a separation of with , and let be a separation of with and . Then
These four lower bounds on the "quadrants" , are the counting core of the proof of Lemma 6.5; the dichotomy that follows uses only them.
Formalization Note The page says the two separations are "- and -balanced"; this is a slip for and , which are the hypotheses of Lemma 6.5 and of the folklore separation, and which are the ones stated here. All quantities are compared as real numbers, since the right-hand sides may be negative.
Preamble
import Mathlib import Definitions.Def_TreewidthApprox_Pushed_Setting
Formal statement
namespace TreewidthApprox.Pushed
theorem four_inequalities {V : Type} [Fintype V] [DecidableEq V] (G : SimpleGraph V)
(k : ℕ) (A₁ B A₂ : Finset V) (hAB : IsSeparation G A₁ B A₂)
(hA₁ : (A₁.card : ℝ) ≤ 3 / 4 * Fintype.card V) (hA₂ : (A₂.card : ℝ) ≤ 3 / 4 * Fintype.card V)
(L X R : Finset V) (hLXR : IsSeparation G L X R) (hX : X.card ≤ k + 1)
(hL : (L.card : ℝ) ≤ 2 / 3 * Fintype.card V) (hR : (R.card : ℝ) ≤ 2 / 3 * Fintype.card V) :
((L ∩ A₁).card : ℝ) + (L ∩ A₂).card + B.card ≥ 1 / 3 * Fintype.card V - (k + 1) ∧
((R ∩ A₁).card : ℝ) + (R ∩ A₂).card + B.card ≥ 1 / 3 * Fintype.card V - (k + 1) ∧
((L ∩ A₁).card : ℝ) + (R ∩ A₁).card + (k + 1) ≥ 1 / 4 * Fintype.card V - B.card ∧
((L ∩ A₂).card : ℝ) + (R ∩ A₂).card + (k + 1) ≥ 1 / 4 * Fintype.card V - B.card := by sorry
end TreewidthApprox.Pushed
Source
Bodlaender, Drange, Dregi, Fomin, Lokshtanov and Pilipczuk, A c^k n 5-approximation algorithm for treewidth, SIAM J. Comput. 45(2) (2016), pp. 369–370, proof of Lemma 6.5, second paragraph (four bulleted inequalities)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.