curiositech/dag-fast-decomposition

SKILL: Fast DAG Decomposition and Reachability

license: Apache-2.0 Name: graph-decomposition-strategies
Description: Apply hierarchical decomposition and structural exploitation strategies from DAG theory to complex system design, problem-solving, and abstraction challenges
Triggers: system scaling problems, dependency management, reachability/connectivity analysis, hierarchical design, performance optimization through preprocessing, abstraction layer design

---

When to Use This Skill

Load this skill when encountering:

• Scaling bottlenecks where brute-force approaches fail but structure exists to exploit
• Dependency resolution problems (build systems, task scheduling, knowledge graphs, import chains)
• Query performance challenges where preprocessing investment could enable fast lookups
• Abstraction design questions about how to layer complex systems
• Optimization paradoxes where "good enough fast" might beat "optimal slow"
• Complexity analysis showing theoretical worst-case doesn't match observed behavior
• Coordination problems where understanding true interdependencies matters more than counting connections

Key signal: When you suspect most of the apparent complexity is redundant structure that could be compressed or bypassed through better decomposition.

---

Core Mental Models

1. Width Over Density: True Complexity Lives in Coordination, Not Connections

The insight: Edge count misleads. The width of a system (maximum number of mutually independent components) reveals true complexity better than connection density.

Why it matters: Dense systems with high edge counts can still have low intrinsic complexity if most edges are transitive (implied by shorter paths). A build system with 10,000 dependency edges might have width 20, meaning at most 20 things truly can't be derived from each other.

Application: When analyzing system complexity, first identify the "reduced edge set" (Ered)—the minimal connections that imply all others. Budget scaling effort against width, not total connections. Systems with low width but high density are ripe for hierarchical compression.

2. Greedy + Fast Beats Optimal + Slow for Compound Workflows

The insight: Near-optimal solutions computed quickly enable their use as preprocessing steps in larger workflows. A 90% optimal solution in 1 second is more valuable than 100% optimal in 1 hour if you need to run it 1000 times or use its output for further computation.

Why it matters: Optimization obsession creates local maxima while missing global efficiency. The paper's heuristics produce chain decompositions within 5-10% of optimal but run orders of magnitude faster, enabling their use in contexts where optimal algorithms would be prohibitive.

Application: For preprocessing, indexing, or iterative workflows, prioritize fast heuristics with quality guarantees over slow exact algorithms. Measure optimization algorithms by downstream value (what they enable), not just solution quality.

3. Hierarchical Abstraction Through Chain Decomposition

The insight: Decomposing a DAG into chains creates natural abstraction levels. Each chain represents a total order (linear hierarchy), while relationships between chains represent coordination boundaries. Reachability within chains is trivial; complexity lives in cross-chain relationships.

Why it matters: This transforms an O(V²) problem (all-pairs reachability) into O(kc * Ered) where kc = chain count and Ered = reduced edges. For graphs where 85-95% of edges are transitive, this is a 10-20x compression of what you need to track.

Application: When designing layered systems, identify "chains" (sequences with clear ordering) and separate them from "coordination points" (where chains must interact). Optimize within chains separately from optimizing across chains. Build indexes at chain boundaries.

4. Transitive Structure as Compression Opportunity

The insight: In dense graphs (average degree > 20), 85-95% of edges are transitive—implied by shorter paths. This isn't a bug; it's structural regularity waiting to be exploited.

Why it matters: Apparent complexity often reflects redundant representation, not inherent difficulty. By identifying and collapsing transitive structure, you can dramatically reduce working set size while preserving all essential information.

Application: In dependency graphs, import chains, knowledge bases, or any transitive relation, explicitly identify which edges are transitive vs. generative. Store and process only the reduced set. Use queries against the reduced set to reconstruct full closure on demand.

5. Invest in Indexing for Query-Heavy Workloads

The insight: Spending O(kc * Ered) time preprocessing to build an index enables O(1) reachability queries. This indexing cost is sublinear in total edges when transitive structure dominates, and the payoff grows with query count.

Why it matters: Systems often face the tradeoff: recompute on every query (no space cost, high time cost per query) vs. precompute everything (O(V²) space, O(1) queries). Chain-based indexing offers a middle path: O(kc * V) space with O(1) queries.

Application: For systems answering many reachability/connectivity queries (access control, dependency checking, routing), invest in structural indexing during preprocessing. The flatter the runtime curve relative to graph density, the better the indexing scheme exploits structure.

---

Decision Frameworks

When Facing Scaling Problems

IF your system's theoretical complexity predicts failure, BUT empirical behavior suggests hidden structure:

• THEN profile to identify transitive vs. generative relationships
• Look for width « node count (high density, low coordination complexity)
• Consider hierarchical decomposition to expose compression opportunities
• Load: hierarchical-abstraction-for-scaling.md

When Choosing Optimization Approaches

IF you need optimal solutions in an interactive or iterative workflow:

• THEN evaluate fast heuristics with quality bounds first
• Measure: heuristic_time * workflow_iterations vs. optimal_time
• Test if 90-95% solution quality is "good enough" for downstream needs
• Load: greedy-decomposition-and-progressive-refinement.md

When Designing Abstraction Layers

IF decomposing a complex system into manageable components:

• THEN identify chains (total orders) vs. coordination points (cross-chain dependencies)
• Measure width to understand true parallelization/independence potential
• Design APIs at chain boundaries, optimize implementations within chains
• Load: width-as-coordination-complexity.md

When Analyzing Graph Performance

IF a dense graph shows better-than-expected algorithmic behavior:

• THEN compute the transitive edge percentage
• If > 80%, structure is highly compressible
• Build on reduced edge set (Ered) rather than full edge set
• Load: transitive-structure-as-compression-opportunity.md

When Building Query Systems

IF you need to answer many connectivity/reachability queries:

• THEN evaluate preprocessing investment vs. query frequency tradeoff
• Chain-based indexing: O(kc * Ered) preprocessing, O(kc * V) space, O(1) queries
• Breakeven: queries > preprocessing_cost / (naive_query_cost - indexed_query_cost)
• Load: constant-time-reachability-through-indexing.md

When Decomposing Complex Problems

IF unsure whether to use top-down or bottom-up decomposition:

• THEN consider hybrid: greedy bottom-up for speed, then iterative refinement
• Path concatenation strategy: start simple, progressively merge where high-value
• Each merge should have asymmetric returns (local cost, global benefit)
• Load: problem-decomposition-strategies.md

---

Reference Table

| Reference File | When to Load | Key Content | |---------------|--------------|-------------| | hierarchical-abstraction-for-scaling.md | Facing scaling problems where flat approaches fail; designing multi-level systems; need to understand how abstraction reduces complexity | Chain decomposition as hierarchical organization; how levels communicate; scaling through structural exploitation | | width-as-coordination-complexity.md | Analyzing true system complexity; designing parallel/distributed systems; estimating coordination overhead | Width definition; relationship to reduced edges; how width predicts scaling behavior; width vs. density | | greedy-decomposition-and-progressive-refinement.md | Choosing between optimization algorithms; designing iterative refinement processes; balancing speed vs. quality | Heuristic vs. exact approaches; path concatenation algorithm; progressive refinement patterns; when "good enough" is better | | transitive-structure-as-compression-opportunity.md | Working with dense graphs; surprising performance results; opportunity to compress working sets | The 85-95% transitive edge finding; implications for storage and computation; how to identify and exploit transitive structure | | constant-time-reachability-through-indexing.md | Designing query systems; preprocessing tradeoff analysis; need for fast lookups | Indexing scheme details; space-time tradeoffs; when to invest in preprocessing; O(1) query performance | | problem-decomposition-strategies.md | Uncertain how to break down complex problems; comparing decomposition approaches; designing modular systems | Top-down vs. bottom-up; hybrid strategies; when each approach works best; decomposition heuristics comparison | | failure-modes-and-structural-blindness.md | Debugging poor performance; understanding when approaches fail; avoiding common pitfalls | Pathological graph structures; when width ≈ V (worst case); hidden assumptions in decomposition strategies |

---

Anti-Patterns

1. Optimizing the Wrong Thing

Symptom: Spending weeks achieving 100% optimal solution when 95% solution computed in seconds would unlock downstream value
Why it fails: Ignores compound workflow effects; local optimization creates global inefficiency
Alternative: Profile the full pipeline; optimize for end-to-end value, not component perfection

2. Treating All Edges Equally

Symptom: Allocating equal storage, computation, or attention to transitive vs. generative edges
Why it fails: Transitive edges are redundant—they're implied by paths through other edges
Alternative: Identify and operate on Ered (reduced edge set); reconstruct transitive closure only when needed

3. Ignoring Width When Estimating Complexity

Symptom: Predicting O(V²) or O(E) behavior without checking if width « V
Why it fails: Width determines true complexity for many graph operations; dense low-width graphs behave much better than edge count suggests
Alternative: Measure width; use width-based complexity estimates (e.g., O(width * V) for reduced edges)

4. Preprocessing Without Query Frequency Analysis

Symptom: Building expensive indexes for systems with few queries, or recomputing on every query when many queries are needed
Why it fails: Wrong tradeoff point; either wasting preprocessing time or query time
Alternative: Estimate query frequency; calculate breakeven point; choose indexing strategy accordingly

5. Flat Decomposition of Hierarchical Problems

Symptom: Treating all components as peers when natural hierarchies exist; building O(n²) cross-component communication
Why it fails: Ignores transitive structure and natural ordering; creates false coordination complexity
Alternative: Identify chains (total orders) first; separate intra-chain logic from inter-chain coordination

6. Seeking Structure in Structureless Graphs

Symptom: Applying hierarchical decomposition to graphs with width ≈ V (e.g., random graphs, cross-product structures)
Why it fails: These techniques exploit low width and high transitivity; benefits vanish when width is high
Alternative: Check structural preconditions (width, transitive percentage) before applying; have fallback strategies

---

Shibboleths: Distinguishing Deep Understanding from Surface Knowledge

Surface-Level Understanding Says:

• "This paper is about an algorithm for chain decomposition of DAGs"
• "The main contribution is faster runtime complexity"
• "It's a graph theory result with limited applicability"

Deep Internalization Reveals Itself Through:

1. Recognizing Width in the Wild

   • Instinctively asking "what's the width?" when analyzing dependency structures
   • Distinguishing between "many connections" (edges) and "many independent concerns" (width)
   • Identifying when apparent complexity is just transitive inflation

2. The Ered Instinct

   • When seeing a dense relationship graph, immediately wondering: "What percentage is transitive?"
   • Building systems that store/process only reduced edges by default
   • Understanding that Ered ≤ width * V is not just a theorem but a design target

3. Preprocessing Calculus

   • Fluidly reasoning about preprocessing cost vs. query frequency tradeoffs
   • Knowing when O(kc * Ered) preprocessing beats O(V²) preprocessing beats no preprocessing
   • Recognizing that "flat runtime curves" (performance independent of density) signal excellent structural exploitation

4. The Greedy Wisdom

   • Defending 90% solutions when they enable compound workflows
   • Articulating why heuristics can be more valuable than optimal algorithms
   • Distinguishing problems where optimality matters from those where speed enables qualitatively different approaches

5. Hierarchical Intuition

   • Naturally decomposing problems into chains (ordered sequences) and coordination points (chain interactions)
   • Seeing that O(1) reachability isn't "impossible"—it's a consequence of good indexing at abstraction boundaries
   • Understanding that hierarchies aren't just organizational—they're computational complexity reducers

6. Structural Awareness

   • Recognizing pathological cases (width ≈ V) where these techniques provide no benefit
   • Knowing that random graphs and cross-product structures defeat hierarchical methods
   • Understanding when structure exists to exploit vs. when brute force is actually optimal

The Telltale Question:

Ask: "Your system has 10,000 dependencies. Is that a lot?"

Surface answer: "Yes, that's very complex."

Deep answer: "What's the width? If width is 50, then Ered ≤ 500,000, and if 90% of the 10,000 edges are transitive, you only have 1,000 generative relationships to track. That might be trivial. But if width is 8,000, you have a genuinely complex coordination problem regardless of edge count."

---

Quick Start

When this skill activates:

1. Identify the graph structure in your problem (nodes = entities, edges = dependencies/relationships/orderings)
2. Estimate width: How many things are truly independent vs. transitively related?
3. Check for transitive dominance: In dense regions, what % of edges are implied by paths?
4. Choose decomposition strategy: Fast heuristic (greedy) or exact algorithm based on downstream needs?
5. If query-heavy: Evaluate preprocessing investment for O(1) lookups
6. Load relevant reference based on your specific bottleneck (see Reference Table)

Remember: The goal isn't to turn everything into a graph problem. It's to recognize when hierarchical decomposition, width-based analysis, or transitive structure exploitation can transform apparent complexity into tractable computation.