# An Algorithm for Deciding if a Set of Observed Independencies Has a Causal Explanation

arXiv: https://arxiv.org/abs/1303.5435 · HTML: https://mlsanity.com/paper/1303.5435/

## Key facts

- Cited by 17 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 13 Mar 2013.

## Built on by (most cited first, 17 of 17)

- [Scalable Intervention Target Estimation in Linear Models](https://mlsanity.com/paper/2111.07512/) (2021)
- [On the Sample Complexity of Causal Discovery and the Value of Domain Expertise](https://mlsanity.com/paper/2102.03274/) (2021)
- [Polynomial-Time Algorithms for Counting and Sampling Markov Equivalent DAGs with Applications](https://mlsanity.com/paper/2205.02654/) (2022)
- [Interventional Causal Discovery in a Mixture of DAGs](https://mlsanity.com/paper/2406.08666/) (2024)
- [Characterization and Learning of Causal Graphs from Hard Interventions](https://mlsanity.com/paper/2505.01037/) (2025)
- [Learning Linear Polytree Structural Equation Models](https://mlsanity.com/paper/2107.10955/) (2021)
- [Practical Algorithms for Orientations of Partially Directed Graphical Models](https://mlsanity.com/paper/2302.14386/) (2023)
- [Introducing Diminutive Causal Structure into Graph Representation Learning](https://mlsanity.com/paper/2406.08709/) (2024)
- [New Rules for Causal Identification with Background Knowledge](https://mlsanity.com/paper/2407.15259/) (2024)
- [Testing Causal Models with Hidden Variables in Polynomial Delay via Conditional Independencies](https://mlsanity.com/paper/2409.14593/) (2024)
- [Modelling Major Disease Outbreaks in the 21st Century: A Causal Approach](https://mlsanity.com/paper/2109.07266/) (2021)
- [Fast Causal Orientation Learning in Directed Acyclic Graphs](https://mlsanity.com/paper/2205.13919/) (2022)
- [Introducing Expertise Logic into Graph Representation Learning from A Causal Perspective](https://mlsanity.com/paper/2301.08496/) (2023)
- [Towards Causal Representation Learning and Deconfounding from Indefinite Data](https://mlsanity.com/paper/2305.02640/) (2023)
- [Counterfactual Explanations of Black-box Machine Learning Models using Causal Discovery with Applications to Credit Rating](https://mlsanity.com/paper/2402.02678/) (2024)
- [Learning linear acyclic causal model including Gaussian noise using ancestral relationships](https://mlsanity.com/paper/2409.00417/) (2024)
- [Lifted Causal Inference](https://mlsanity.com/paper/2606.28024/) (2026)

## Abstract (arXiv)

In a previous paper [Pearl and Verma, 1991] we presented an algorithm for extracting causal influences from independence information, where a causal influence was defined as the existence of a directed arc in all minimal causal models consistent with the data. In this paper we address the question of deciding whether there exists a causal model that explains ALL the observed dependencies and independencies. Formally, given a list M of conditional independence statements, it is required to decide whether there exists a directed acyclic graph (dag) D that is perfectly consistent with M, namely, every statement in M, and no other, is reflected via dseparation in D. We present and analyze an effective algorithm that tests for the existence of such a day, and produces one, if it exists.