Proof of Lemma 2.9 — a component lies in one part
ProvedTreewidthApprox.Partition.comp_subset_partbalanced-partitiongraph-componentgraph-theoryp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1
Let be disjoint vertex sets that cover , with no graph edge between distinct parts. Every connected component of that meets lies wholly inside , for :
This supplies the component containment used in one direction of Lemma 2.9.
Formalization Note Empty parts are allowed. The three unordered pairs express the paper's condition for all , using symmetry of a simple graph.
Preamble
import Mathlib import Definitions.Def_TreewidthApprox_Partition_Setting
Formal statement
namespace TreewidthApprox.Partition
/-- Proof of Lemma 2.9, p. 364: when the parts partition `G \ X` with no
cross edges, each component lies wholly in the part containing its starting vertex. -/
theorem comp_subset_part {V : Type} [Fintype V] [DecidableEq V]
(G : SimpleGraph V) (X M₁ M₂ M₃ : Finset V)
(hpart : Disjoint M₁ M₂ ∧ Disjoint M₁ M₃ ∧ Disjoint M₂ M₃ ∧
M₁ ∪ M₂ ∪ M₃ = Finset.univ \ X)
(hedge : TreewidthApprox.Pushed.NoEdge G M₁ M₂ ∧ TreewidthApprox.Pushed.NoEdge G M₁ M₃ ∧ TreewidthApprox.Pushed.NoEdge G M₂ M₃) :
(∀ u ∈ M₁, TreewidthApprox.Pushed.avoidComp G X u ⊆ M₁) ∧
(∀ u ∈ M₂, TreewidthApprox.Pushed.avoidComp G X u ⊆ M₂) ∧
(∀ u ∈ M₃, TreewidthApprox.Pushed.avoidComp G X u ⊆ M₃) := by sorry
end TreewidthApprox.Partition
Source
Bodlaender, Drange, Dregi, Fomin, Lokshtanov and Pilipczuk, A c^k n 5-approximation algorithm for treewidth, SIAM J. Comput. 45(2) (2016), p. 364, proof of Lemma 2.9, first paragraph, https://doi.org/10.1137/130947374
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.