Proof of Lemma 6.5, p. 369 — restricting (L, X, R) to G₁, G₂ gives terminal separations of orders |X ∩ A₁|, |X ∩ A₂|
ProvedTreewidthApprox.Pushed.restrict_terminal_sepgraph-separationp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1terminal-separationtreewidth
This is the step of the proof of Lemma 6.5 that establishes part (i).
Let and be two separations of a finite graph . Put
and for let with terminals . Then:
- is a terminal separation of of order ;
- is a terminal separation of of order ;
- .
The paper phrases items 1–2 as " and are terminal separations in and ", naming each separation by its middle part. Item 3 is the budget identity behind when .
Formalization Note is encoded by its vertex set (see the definitions file).
Preamble
import Mathlib import Definitions.Def_TreewidthApprox_Pushed_Setting
Formal statement
namespace TreewidthApprox.Pushed
theorem restrict_terminal_sep {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) :
IsTerminalSep G (A₁ ∪ (B \ (X ∩ B))) (L ∩ B) (R ∩ B) (X ∩ A₁).card
(L ∩ (A₁ ∪ B)) (X ∩ A₁) (R ∩ (A₁ ∪ B)) ∧
IsTerminalSep G (A₂ ∪ (B \ (X ∩ B))) (L ∩ B) (R ∩ B) (X ∩ A₂).card
(L ∩ (A₂ ∪ B)) (X ∩ A₂) (R ∩ (A₂ ∪ B)) ∧
(X ∩ A₁).card + (X ∩ A₂).card + (X ∩ B).card = X.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. 369, proof of Lemma 6.5, first paragraph
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.