Finite parent-pointer certificates for tree decompositions
DefinitionStableMSR_Recovery_Supplement_ParentBagCertificatesalgorithmsclustering
Keys carry a natural depth. Parents strictly decrease depth away from the root. Each graph vertex has a distinguished home bag, and every other occurrence is also present in its parent. The certificate also covers every edge and bounds bag sizes.
Definition code
import Definitions.Def_StableMSR_Recovery_Supplement_TightBlockPolicies
set_option autoImplicit false
namespace StableMSR.Recovery.Supplement.BinaryRecovery.Regional.BlockSearch
abbrev Key := ℕ × ℕ
def zeroKey : Key := (0,0)
def keyEq (a b : Key) := decide (a.1=b.1) && decide (a.2=b.2)
def parentLayout (ks : List Key) (up : Key→Key) (bag : Key→Block) : FactorLayout :=
ks.map fun p => (bag p,(List.range ks.length).filter (fun j=>keyEq (ks[j]?.getD zeroKey) (up p)))
def ParentCertificate (z : GraphInput) (t : ℕ) (ks : List Key) (up : Key→Key) (bag : Key→Block) : Prop :=
let G := scopeGraph z.1 z.2
let B := fun p => cuts z (bag p)
ks.Nodup ∧ zeroKey∈ks ∧ up zeroKey=zeroKey ∧
(∀p∈ks,p≠zeroKey → up p∈ks ∧ (up p).1<p.1) ∧
(∀p∈ks,(B p).card≤t+1) ∧
(∀x y,G.Adj x y → ∃p∈ks,x∈B p ∧ y∈B p) ∧
∃home : Vertex z→Key, (∀x,home x∈ks ∧ x∈B (home x)) ∧
∀p∈ks,∀x∈B p,p≠home x → p≠zeroKey ∧ x∈B (up p)
end StableMSR.Recovery.Supplement.BinaryRecovery.Regional.BlockSearch
Source
Explicit graph encoding for tight-block witness reconstruction.