Finite tight-block decomposition search
DefinitionStableMSR_DecompositionSearch_RecurrenceThe depth-bounded search accepts a block at positive depth if a bag of at most vertices contains , lies in , introduces a vertex of , and each resulting connected component is accepted at smaller depth with its exact external boundary of size at most . Depth zero rejects. Global recognition tests all components of with empty boundary at depth . These finite recurrences express search success and do not assert an instruction-level implementation.
Definition code
import Definitions.Def_StableMSR_TightBlockSearch
namespace StableMSR.Recovery.DecompositionSearch
variable {V : Type} [Fintype V] [DecidableEq V]
noncomputable def accepts (G : SimpleGraph V) (w : ℕ) : ℕ → Finset V → Finset V → Prop
| 0, _, _ => False
| m+1, S, C => ∃ B : Finset V,
S ⊆ B ∧ B ⊆ S ∪ C ∧ B.card ≤ w+1 ∧ (B ∩ C).Nonempty ∧
∀ D ∈ children G B C,
(boundary G D).card ≤ w ∧ accepts G w m (boundary G D) D
noncomputable def recognizes (G : SimpleGraph V) (w : ℕ) : Prop :=
∀ C ∈ PartialDecompositions.components G ∅,
accepts G w (Fintype.card V) ∅ C
end StableMSR.Recovery.DecompositionSearch
Source
Finite-state bounded-treewidth decomposition construction supporting the Prove2Me Exact Sum-of-Radii Clustering under Any Constant Stability mission.