Flooding enumerates precisely the components left by a separator
ProvedStableMSR.Recovery.Supplement.BinaryRecovery.Regional.BlockSearch.binary_deleted_componentsalgorithmsclusteringdynamic-programming
Starting from every surviving input vertex, flood for at most the input-list length. The resulting list represents exactly every connected component after deleting the separator.
Preamble
import Definitions.Def_StableMSR_Recovery_Supplement_BinaryBlockSearch open StableMSR.Recovery StableMSR.Recovery.Supplement.BinaryRecovery open StableMSR.Recovery.Supplement.BinaryRecovery.Regional open StableMSR.Recovery.Supplement.BinaryRecovery.Regional.BlockSearch open StableMSR.Recovery.DecompositionSearch RobertsonSeymour1986.GM5
Formal statement
theorem StableMSR.Recovery.Supplement.BinaryRecovery.Regional.BlockSearch.binary_deleted_components (z : GraphInput) (s : Block) (C : Finset (Vertex z)) :
C∈PartialDecompositions.components (scopeGraph z.1 z.2) (cuts z s) ↔
∃c∈BlockSearch.pieces z s,cuts z c=C := by
sorry
Source
Constructive binary implementation of the tight-block recurrence in StableMSR.Recovery.DecompositionSearch.finite_decomposition_search, https://prove2.me/theorems/d4f2a14a-b18f-44f7-966a-d1411797cf17.