Recover the treewidth promise on the explicit primal graph
ProvedStableMSR.Recovery.Supplement.BinaryRecovery.Regional.canonical_scope_graph_widthalgorithmsclusteringdynamic-programming
For a list of variables and a list of factor scopes, the labelled width promise is equivalent to validity of the names and bounded treewidth of the explicit graph joining distinct labels co-occurring in a scope. Repeated names and repeated scopes are allowed.
Preamble
import Definitions.Def_StableMSR_Recovery_Supplement_ScopeGraph open StableMSR.Recovery.Supplement.BinaryRecovery.Regional open RobertsonSeymour1986.GM5
Formal statement
theorem StableMSR.Recovery.Supplement.BinaryRecovery.Regional.canonical_scope_graph_width (vs : Block) (scopes : List Block) (t : ℕ) :
ScopeWidth vs scopes t ↔
(∀u∈scopes,∀v∈u,v∈vs) ∧ TreewidthLE (scopeGraph vs scopes) t := by
sorry
Source
Supplement to the bounded-width factor algorithm for stable sum of radii, explicit primal graph.