Gateways to Tractability for Satisfiability in Pearl’s Causal Hierarchy

Robert Ganian, Marlene Gründel, Simon Wietheger
Proceedings of the 43rd International Conference on Machine Learning, PMLR 306:32958-32968, 2026.

Abstract

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.

Cite this Paper

BibTeX
@InProceedings{pmlr-v306-ganian26a, title = {Gateways to Tractability for Satisfiability in Pearl’s Causal Hierarchy}, author = {Ganian, Robert and Gr\"{u}ndel, Marlene and Wietheger, Simon}, booktitle = {Proceedings of the 43rd International Conference on Machine Learning}, pages = {32958--32968}, year = {2026}, editor = {Zhang, Tong and Dudik, Miroslav and Jaggi, Martin and Agarwal, Alekh and Li, Sharon and Schuurmans, Dale and Zhu, Jerry and Berkenkamp, Felix and Dong, Hanze and Bietti, Alberto}, volume = {306}, series = {Proceedings of Machine Learning Research}, month = {06--11 Jul}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/v306/main/assets/ganian26a/ganian26a.pdf}, url = {https://proceedings.mlr.press/v306/ganian26a.html}, abstract = {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.} }
Endnote
%0 Conference Paper %T Gateways to Tractability for Satisfiability in Pearl’s Causal Hierarchy %A Robert Ganian %A Marlene Gründel %A Simon Wietheger %B Proceedings of the 43rd International Conference on Machine Learning %C Proceedings of Machine Learning Research %D 2026 %E Tong Zhang %E Miroslav Dudik %E Martin Jaggi %E Alekh Agarwal %E Sharon Li %E Dale Schuurmans %E Jerry Zhu %E Felix Berkenkamp %E Hanze Dong %E Alberto Bietti %F pmlr-v306-ganian26a %I PMLR %P 32958--32968 %U https://proceedings.mlr.press/v306/ganian26a.html %V 306 %X 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.
APA
Ganian, R., Gründel, M. & Wietheger, S.. (2026). Gateways to Tractability for Satisfiability in Pearl’s Causal Hierarchy. Proceedings of the 43rd International Conference on Machine Learning, in Proceedings of Machine Learning Research 306:32958-32968 Available from https://proceedings.mlr.press/v306/ganian26a.html.

Related Material