Proof of Lemma 6.5, p. 370 — either |L ∩ A₁|, |R ∩ A₂| ≥ ε or |L ∩ A₂|, |R ∩ A₁| ≥ ε, ε = ⅛|V(G)| − (|B|+(k+1))/2
ProvedTreewidthApprox.Pushed.dichotomybalanced-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 . Write
Then at least one of the following holds:
- and ;
- and .
In the proof of Lemma 6.5 this lets one assume, after possibly exchanging the roles of and , that meets and meets in at least vertices each; that is what bounds the sides of the glued separation by .
Formalization Note is a real number and may be negative (then the claim is trivial); all comparisons are over the reals.
Preamble
import Mathlib import Definitions.Def_TreewidthApprox_Pushed_Setting
Formal statement
namespace TreewidthApprox.Pushed
theorem dichotomy {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) :
((1 / 8 * (Fintype.card V : ℝ) - ((B.card : ℝ) + (k + 1)) / 2) ≤ (L ∩ A₁).card ∧
(1 / 8 * (Fintype.card V : ℝ) - ((B.card : ℝ) + (k + 1)) / 2) ≤ (R ∩ A₂).card) ∨
((1 / 8 * (Fintype.card V : ℝ) - ((B.card : ℝ) + (k + 1)) / 2) ≤ (L ∩ A₂).card ∧
(1 / 8 * (Fintype.card V : ℝ) - ((B.card : ℝ) + (k + 1)) / 2) ≤ (R ∩ A₁).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), p. 370, proof of Lemma 6.5, the claim after the four inequalities
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.