Structured Decompositions

Structured Decompositions Skill

Functorial structured decompositions for compositional problem solving via sheaf-theoretic methods. Based on AlgebraicJulia/StructuredDecompositions.jl.

Core Principle: Decompose → Lift → Solve Locally → Reassemble

Hard global problems become tractable when:

1. Decompose: Break input into overlapping bags connected via adhesions
2. Lift: Apply functor 𝐃 to promote problem F: C → E to 𝐃F: 𝐃C → 𝐃E
3. Solve Locally: Compute on bags, enforce consistency at adhesions via pullback
4. Reassemble: Sheaf condition guarantees global solution from local pieces

Key Types

abstract type StructuredDecomposition{G, C, D} <: Diagram{id, C, D} end

@data DecompType begin
  Decomposition     # d: FG → Span C (contravariant)
  CoDecomposition   # d: FG → Cospan C^op (covariant)
end

struct StrDecomp{G, C, D} <: StructuredDecomposition{G, C, D}  
  decomp_shape ::G   # Shape graph (tree for tree decompositions)
  diagram      ::D   # Functor mapping shape to category C
  decomp_type  ::DecompType
  domain       ::C   # Category of elements ∫G
end

Decomposition Anatomy

Bag₁ ←─[Adhesion₁₂]─→ Bag₂ ←─[Adhesion₂₃]─→ Bag₃

Each adhesion is a SPAN: Bag_i ← Apex → Bag_j
  - Apex encodes overlap/interface between bags
  - Morphisms are inclusion maps

Essential Operations

Functorial Lifting (The Key Insight)

𝐃(f, d::StructuredDecomposition, t::DecompType)::StructuredDecomposition

If F encodes a computational problem, 𝐃(F, d) promotes global computation to local computation on decomposition parts.

Sheaf Decision Algorithm

decide_sheaf_tree_shape(f, d::StructuredDecomposition) → (Bool, Witness)

Algorithm:

1. Lift problem f to decomposition level: 𝐃(f, d, CoDecomposition)
2. For each adhesion edge:
   • Extract cospan: dx₁ → de ← dx₂
   • Compute pullback cone with legs l₁, l₂
   • Project images: im(l₁), im(l₂)
   • Replace apex with image intersection
3. If any bag empty → (false, witness), else (true, witness)

Adhesion Filter (Core Mechanism)

function adhesion_filter(i::Integer, d::StructuredDecomposition)
  # Fetch cospan dx₁ → de ← dx₂
  (csp, d_csp) = adhesionSpans(d, true)[i]
  
  # Pullback cone
  p_cone = pullback(d_csp)
  p_legs = legs(p_cone)
  
  # Project to images
  imgs = force.(map(f -> legs(image(f))[1], p_legs))
  
  # New cospan with filtered apex
  new_d_csp = force.(map(t -> compose(t...), zip(imgs, d_csp)))
  
  # Rebuild decomposition with filtered span
  StrDecomp(d.decomp_shape, new_diagram, d.decomp_type)
end

Width-Parameterized Complexity

Problems encoded as sheaves solve in FPT time parameterized by decomposition width:

• Treewidth k: Largest bag has k+1 vertices
• Complexity: O(n · f(k)) where f depends only on width

Pattern: Graph Coloring

struct Coloring; n::Int; end

function (c::Coloring)(graph::SymmetricGraph)
  FinSet(homomorphisms(graph, K(c.n)))
end

function (c::Coloring)(f::ACSetTransformation)
  FinFunction(λ -> compose(f, λ), c(codom(f)), c(dom(f)))
end

# Solve
graph = path_graph(SymmetricGraph, 100)
decomp = StrDecomp(graph)
result = decide_sheaf_tree_shape(skeleton ∘ Coloring(3), decomp)

Connection to OlmoEarth Shared Protentions

When to Use

✅ Good fit:

• Decision problems on graphs with bounded treewidth
• Constraint satisfaction with sparse constraint graphs
• Compositional verification of distributed systems
• Multi-agent coordination with local observations

❌ Poor fit:

• Dense graphs (treewidth ≈ n)
• Problems without sheaf structure

Local Source

/Users/bob/ies/StructuredDecompositions.jl/

End-of-Skill Interface

Integration with Other Skills

• acsets-algebraic-databases: Objects being decomposed are ACSets
• gay-mcp: GF(3) conservation across decomposition bags
• world-hopping: Decomposition as possible world navigation
• bisimulation-game: Sheaf consistency as bisimulation condition

References

1. Structured Decompositions Paper
2. Tree Decompositions
3. Sheaf Theory

Autopoietic Marginalia

The interaction IS the skill improving itself.

Every use of this skill is an opportunity for worlding:

• MEMORY (-1): Record what was learned
• REMEMBERING (0): Connect patterns to other skills
• WORLDING (+1): Evolve the skill based on use

Add Interaction Exemplars here as the skill is used.