Structural Tractability in Causal Dependency Graphs

You are reading version 1 of this direction, frozen 2026-10-04. The latest version is version 2.

Version 1 of 231 papers70 conceptsfrozen 2026-10-04

Most problems in automated planning and causal reasoning are computationally daunting, often categorized as NP-hard, PSPACE-complete, or even undecidable. However, real-world systems often possess an underlying structure that is far simpler than the worst-case scenarios suggest. Researchers have spent decades mapping "islands of tractability"—specific structural configurations where these hard problems can be solved in polynomial time.

The core insight across this research is that the complexity of reasoning is not just a function of the number of variables, but of the topology of their dependencies. By restricting the shape of the causal graph and the complexity of individual variables, we can transform exponential search spaces into manageable, linear-time tasks.

The Causal Graph as a Map of Complexity

At the heart of this direction is the causal graph, a directed graph where nodes represent state variables and edges represent dependencies (e.g., an action changing variable $A$ requires variable $B$ to be in a certain state). Ronen I. Brafman and Carmel Domshlak established in Factored Planning: How, When, and When Not that the complexity of planning is primarily governed by the treewidth of this graph.

Treewidth measures how "tree-like" a graph is. When dependencies form a tree or a low-width structure, we can use "divide-and-conquer" strategies—factoring the problem into independent sub-problems that are solved locally and then merged. This structural simplicity is the primary "gateway to tractability" for problems ranging from causal satisfiability Robert Ganian, Marlene Gründel, and Simon Wietheger in Gateways to Tractability for Satisfiability in Pearl's Causal Hierarchy to determining responsibility in team plans Joseph Halpern and Brian Logan 0001 in Causality, Responsibility and Blame in Team Plans.

The Fragile Boundary of Domain Size

A recurring and counter-intuitive finding is that graph structure alone does not guarantee efficiency. The domain size—the number of possible values a variable can take—acts as a critical threshold.

In Structural Patterns Beyond Forks, Michael Katz and Emil Keyder demonstrate this "complexity cliff" using the fork structure (one root variable influencing multiple leaves). If the root variable is binary (two states), the problem is tractable. If it becomes ternary (three states), the problem suddenly becomes NP-complete.

Why? Because a variable with a large domain can "encode" complex logic, effectively hiding a hard combinatorial problem inside a single node. As Eduard Eiben and Sebastian Ordyniak note in Unary Integer Linear Programming with Structural Restrictions, large domains allow a single central node to consolidate information from across the graph, neutralizing the benefits of a sparse interaction structure.

Identifying Tractable Topologies

Beyond simple trees, researchers have identified a hierarchy of shapes that permit efficient reasoning:

  • Polytrees: Directed acyclic graphs where there is at most one undirected path between any two nodes. Meysam Aghighi and Peter Jonsson showed in Tractable Cost-Optimal Planning over Restricted Polytree Causal Graphs that optimal planning is polynomial if the polytree has bounded domain size and diameter.
  • Hourglasses and Semiforks: More complex mediated structures that remain tractable as long as actions depend on only one variable at a time (1-dependence).
  • Root and Leaf Restrictions: In numeric planning, which is generally undecidable, Alexander Shleyfman and Daniel Gnad 0001 proved in Structurally Restricted Fragments of Numeric Planning that if numeric variables are restricted to being "roots" (no dependencies) or "leaves" (no dependents), the problem becomes decidable and falls into the same complexity class as classical planning.

Parameterized Complexity: Isolating the Hardness

When a problem is "hard," it isn't necessarily hard in every dimension. Parameterized complexity allows researchers to isolate the source of the explosion. By treating parameters like plan length or structural depth as separate from the input size, they can find algorithms that are "Fixed-Parameter Tractable" (FPT).

For example, Christer Bäckström and Sebastian Ordyniak have shown that many planning problems are FPT relative to the target plan length The Complexity of Planning Revisited. This explains why heuristics often work well in practice: if the solution is short, the "hardness" of the general problem doesn't have room to manifest.

Similarly, Novel Structural Parameters for Acyclic Planning Using Tree Embeddings introduces up-depth and down-depth, measuring how "shallowly" a graph can be embedded into a tree. These parameters bound how many times a variable must change state, preventing the state-space explosion that typically occurs in deep dependency chains.

Practical Applications: From Games to Heuristics

These theoretical "islands" are not just mathematical curiosities; they drive practical AI performance.

  • Heuristics: The Red-Black Relaxed Plan Heuristics by Michael Katz 0001 and Jörg Hoffmann 0001 uses structural tractability to create more accurate "relaxed" plans, significantly speeding up search in complex domains.
  • Real-time Systems: In Topological Planning with Post-unique and Unary Actions, Guillaume Prévost and colleagues demonstrate that by enforcing strict topological constraints, a planner can generate millions of plans per frame for video game NPCs, turning an exponential search into a linear topological sort.

By identifying the exact structural boundaries where complexity transitions from polynomial to exponential, this research provides the blueprint for building AI that is both theoretically grounded and computationally efficient.

Papers in this version

History & citationVersion 2 · 2026-10-04

Current · Permanent link

  1. Version 2 (latest) · 2026-10-04 · 38 papers
  2. Version 1 · 2026-10-04 · 31 papers
Cite this direction

Latest version (a living page):

@misc{lacuna_planning_to_csp_reduction_de7ce92c,
  title = {planning-to-CSP reduction},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/planning-to-csp-reduction/rdr_de7ce92c53dd4b59b5e32c40b50aeeb9},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-22},
}

This exact version (version 1, frozen text):

@misc{lacuna_structural_tractability_in_causal_depend_de7ce92c_v1,
  title = {Structural Tractability in Causal Dependency Graphs},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/structural-tractability-in-causal-dependency-graphs/rdr_de7ce92c53dd4b59b5e32c40b50aeeb9/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-22},
}