Lemma 6.5 (ii), p. 369 — a left-pushed and a right-pushed terminal separation glue to a terminal separation of G of order ≤ k+1
ProvedTreewidthApprox.Pushed.glue_terminal_sepgraph-separationp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1terminal-separationtreewidth
This is the first assertion of Lemma 6.5 (ii).
Let be a separation of a finite graph , let be a partition of , and let be integers with . Let and , both with terminals . If is a left-pushed terminal separation of of order and is a right-pushed terminal separation of of order , then
is a terminal separation of (with terminals ) of order at most .
The conclusion in fact holds for any terminal separations of and of orders and ; pushedness is only needed for the size bounds of Lemma 6.5. The statement keeps the paper's hypotheses.
Formalization Note is encoded by its vertex set; a terminal separation of itself is one with vertex set .
Preamble
import Mathlib import Definitions.Def_TreewidthApprox_Pushed_Setting
Formal statement
namespace TreewidthApprox.Pushed
theorem glue_terminal_sep {V : Type} [Fintype V] [DecidableEq V] (G : SimpleGraph V)
(A₁ B A₂ : Finset V) (hAB : IsSeparation G A₁ B A₂)
(TL XB TR : Finset V) (hpart : IsPartition3 B TL XB TR)
(k k₁ k₂ : ℕ) (hbudget : k₁ + k₂ + XB.card ≤ k + 1)
(L₁ X₁ R₁ L₂ X₂ R₂ : Finset V)
(h₁ : IsLeftPushed G (A₁ ∪ (B \ XB)) TL TR k₁ L₁ X₁ R₁)
(h₂ : IsRightPushed G (A₂ ∪ (B \ XB)) TL TR k₂ L₂ X₂ R₂) :
IsTerminalSep G Finset.univ TL TR (k + 1) (L₁ ∪ TL ∪ L₂) (X₁ ∪ XB ∪ X₂) (R₁ ∪ TR ∪ R₂) := 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, Lemma 6.5 (ii), first assertion
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.