Restrict a partial decomposition through a minimum separator without increasing bags
ProvedMazoit2013.minimum_separator_routingLet a graph have a partial tree decomposition at threshold b, rooted at a leaf. Let S be a minimum-cardinality separator between the root bag and a target set, and B a retained side containing S and the target. Assume the root bag meets B only inside S, every edge entering B enters through S, and S has size at most b. There is a partial decomposition of the graph induced by B on the same tree, with root bag exactly S and every bag no larger than before. Every resulting flap is contained in an original flap other than the selected root flap. The construction routes separator vertices along tree paths; its size bound follows directly from separator minimality, without a vertex-disjoint-paths theorem. This is the complete one-side modification used in partial-decomposition gluing.
import Definitions.Def_Mazoit2013_PartialDecompositions open RobertsonSeymour1986.GM5 StableMSR.Recovery.PartialDecompositions
theorem Mazoit2013.minimum_separator_routing {V T : Type} [Fintype V] [DecidableEq V] [DecidableEq T]
{G : SimpleGraph V} {tree : SimpleGraph T} {bags : T → Finset V} {b : ℕ}
(h : IsPartial G b tree bags) (B S target : Finset V) (root u : T)
(hSb : S.card ≤ b) (hSB : S ⊆ B) (htarget : target ⊆ B)
(hroot : bags root ∩ B ⊆ S) (hleaf : ∀ z, tree.Adj root z → z = u)
(hboundary : ∀ x, x ∉ B → ∀ y, G.Adj x y → y ∈ B → y ∈ S)
(hmin : ∀ D : Finset V,
(∀ x ∈ bags root, ∀ y ∈ target, ∀ p : G.Walk x y, ∃ z ∈ p.support, z ∈ D) →
S.card ≤ D.card) :
∃ newbags : T → Finset V,
newbags root = S ∧ (∀ t, newbags t ⊆ B) ∧
(∀ t, (newbags t).card ≤ (bags t).card) ∧
IsPartial (G.induce (B : Set V)) b tree (fun t => (newbags t).subtype (· ∈ B)) ∧
∀ C ∈ flaps b tree newbags,
∃ A ∈ flaps b tree bags, A ≠ bags root \ bags u ∧ C ⊆ A := by sorry