Proof of Lemma 6.5, p. 370 — pushed separations dominate the restriction of (L, X, R): |L₁ ∩ A₁| ≥ |L ∩ A₁|, |R₂ ∩ A₂| ≥ |R ∩ A₂|
ProvedTreewidthApprox.Pushed.pushed_gegraph-separationp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1terminal-separationtreewidth
Let and be two separations of a finite graph , and set, as in the proof of Lemma 6.5,
with carrying terminals . Then
- every left-pushed terminal separation of of order satisfies ;
- every right-pushed terminal separation of of order satisfies .
Together with the dichotomy (in the case ) this gives , which bounds the sides of the glued separation in Lemma 6.5.
Formalization Note is encoded by its vertex set ; pushedness compares with all terminal separations of of order at most with the same terminals.
Preamble
import Mathlib import Definitions.Def_TreewidthApprox_Pushed_Setting
Formal statement
namespace TreewidthApprox.Pushed
theorem pushed_ge {V : Type} [Fintype V] [DecidableEq V] (G : SimpleGraph V)
(A₁ B A₂ : Finset V) (hAB : IsSeparation G A₁ B A₂)
(L X R : Finset V) (hLXR : IsSeparation G L X R) :
(∀ L₁ X₁ R₁ : Finset V,
IsLeftPushed G (A₁ ∪ (B \ (X ∩ B))) (L ∩ B) (R ∩ B) (X ∩ A₁).card L₁ X₁ R₁ →
(L ∩ A₁).card ≤ (L₁ ∩ A₁).card) ∧
(∀ L₂ X₂ R₂ : Finset V,
IsRightPushed G (A₂ ∪ (B \ (X ∩ B))) (L ∩ B) (R ∩ B) (X ∩ A₂).card L₂ X₂ R₂ →
(R ∩ A₂).card ≤ (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, last paragraph
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.