Gateways to Tractability for Satisfiability in Pearl's Causal Hierarchy
This addresses a fundamental challenge in causal reasoning for researchers in AI and statistics, providing new algorithmic tools, though it is incremental in advancing parameterized approaches.
The paper tackled the computationally intractable satisfiability problem for formulas in Pearl's Causal Hierarchy by identifying the first gateways to tractability using parameterized complexity. It resulted in fixed-parameter and XP-algorithms for key fragments, with matching hardness results to map tractability limits.
Pearl's Causal Hierarchy (PCH) is a central framework for reasoning about probabilistic, interventional, and counterfactual statements, yet the satisfiability problem for PCH formulas is computationally intractable in almost all classical settings. We revisit this challenge through the lens of parameterized complexity and identify the first gateways to tractability. Our results include fixed-parameter and XP-algorithms for satisfiability in key probabilistic and counterfactual fragments, using parameters such as primal treewidth and the number of variables, together with matching hardness results that map the limits of tractability. Technically, we depart from the dynamic programming paradigm typically employed for treewidth-based algorithms and instead exploit structural characterizations of well-formed causal models, providing a new algorithmic toolkit for causal reasoning.