Asi structured-decomp

StructuredDecompositions.jl: Sheaves on tree decompositions for FPT algorithms

install

source · Clone the upstream repo

git clone https://github.com/plurigrid/asi

Claude Code · Install into ~/.claude/skills/

T=$(mktemp -d) && git clone --depth=1 https://github.com/plurigrid/asi "$T" && mkdir -p ~/.claude/skills && cp -r "$T/ies/music-topos/.agents/skills/structured-decomp" ~/.claude/skills/plurigrid-asi-structured-decomp && rm -rf "$T"

manifest: ies/music-topos/.agents/skills/structured-decomp/SKILL.md

source content

Structured Decompositions Skill

Core Concepts

StrDecomp = Functor

d: ∫G → C

where:

∫G = category of elements of shape graph
C = target category (Graph, FinSet, etc.)

using StructuredDecompositions

# Create decomposition from graph
d = StrDecomp(graph)

# Access components
bags(d)           # Local substructures
adhesions(d)      # Overlaps
adhesionSpans(d)  # Span morphisms

The 𝐃 Functor

Lifts decision problems to decomposition space:

# Define problem as functor
k_coloring(G) = homomorphisms(G, K_k)

# Lift and solve
solution = 𝐃(k_coloring, decomp, CoDecomposition)
(answer, _) = decide_sheaf_tree_shape(k_coloring, decomp)

FPT Complexity

Runtime: O(f(width) × n) where width = max adhesion size

GF(3) Triads

dmd-spectral (-1) ⊗ structured-decomp (0) ⊗ koopman-generator (+1) = 0 ✓
sheaf-cohomology (-1) ⊗ structured-decomp (0) ⊗ colimit-reconstruct (+1) = 0 ✓

References

Bumpus et al. arXiv:2207.06091
algebraicjulia.github.io/StructuredDecompositions.jl