# Learning Sparse Causal Models is not NP-hard

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

## Key facts

- Cited by 49 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 26 Sep 2013.

## Built on by (most cited first, 30 of 49)

- [A survey of Bayesian Network structure learning](https://mlsanity.com/paper/2109.11415/) (2021)
- [Causal Structure Learning: a Combinatorial Perspective](https://mlsanity.com/paper/2206.01152/) (2022)
- [Causal Interpretation of Self-Attention in Pre-Trained Transformers](https://mlsanity.com/paper/2310.20307/) (2023)
- [Recursive Causal Structure Learning in the Presence of Latent Variables and Selection Bias](https://mlsanity.com/paper/2110.12036/) (2021)
- [Iterative Causal Discovery in the Possible Presence of Latent Confounders and Selection Bias](https://mlsanity.com/paper/2111.04095/) (2021)
- [Differentiable Causal Discovery Under Latent Interventions](https://mlsanity.com/paper/2203.02336/) (2022)
- [Local Constraint-Based Causal Discovery under Selection Bias](https://mlsanity.com/paper/2203.01848/) (2022)
- [Causal Reasoning in the Presence of Latent Confounders via Neural ADMG Learning](https://mlsanity.com/paper/2303.12703/) (2023)
- [Causal Discovery with Fewer Conditional Independence Tests](https://mlsanity.com/paper/2406.01823/) (2024)
- [Learning Bayesian Networks in the Presence of Structural Side Information](https://mlsanity.com/paper/2112.10884/) (2021)
- [DRCFS: Doubly Robust Causal Feature Selection](https://mlsanity.com/paper/2306.07024/) (2023)
- [Toward Falsifying Causal Graphs Using a Permutation-Based Test](https://mlsanity.com/paper/2305.09565/) (2023)
- [Generalized Independent Noise Condition for Estimating Causal Structure with Latent Variables](https://mlsanity.com/paper/2308.06718/) (2023)
- [Local Causal Structure Learning in the Presence of Latent Variables](https://mlsanity.com/paper/2405.16225/) (2024)
- [Novel Ordering-based Approaches for Causal Structure Learning in the Presence of Unobserved Variables](https://mlsanity.com/paper/2208.06935/) (2022)
- [Deconfounded Score Method: Scoring DAGs with Dense Unobserved Confounding](https://mlsanity.com/paper/2103.15106/) (2021)
- [From Temporal to Contemporaneous Iterative Causal Discovery in the Presence of Latent Confounders](https://mlsanity.com/paper/2306.00624/) (2023)
- [Local Discovery by Partitioning: Polynomial-Time Causal Discovery Around Exposure-Outcome Pairs](https://mlsanity.com/paper/2310.17816/) (2023)
- [Expert-Aided Causal Discovery of Ancestral Graphs](https://mlsanity.com/paper/2309.12032/) (2023)
- [FRITL: A Hybrid Method for Causal Discovery in the Presence of Latent Confounders](https://mlsanity.com/paper/2103.14238/) (2021)
- [Improving Efficiency and Accuracy of Causal Discovery Using a Hierarchical Wrapper](https://mlsanity.com/paper/2107.05001/) (2021)
- [Local Causal Discovery for Structural Evidence of Direct Discrimination](https://mlsanity.com/paper/2405.14848/) (2024)
- [A Causal World Model Underlying Next Token Prediction: Exploring GPT in a Controlled Environment](https://mlsanity.com/paper/2412.07446/) (2024)
- [Causal Inference in medicine and in health policy, a summary](https://mlsanity.com/paper/2105.04655/) (2021)
- [CLEAR: Causal Explanations from Attention in Neural Recommenders](https://mlsanity.com/paper/2210.10621/) (2022)
- [Front-door Adjustment Beyond Markov Equivalence with Limited Graph Knowledge](https://mlsanity.com/paper/2306.11008/) (2023)
- [Embracing Discrete Search: A Reasonable Approach to Causal Structure Learning](https://mlsanity.com/paper/2510.04970/) (2025)
- [s-ID: Causal Effect Identification in a Sub-Population](https://mlsanity.com/paper/2309.02281/) (2023)
- [Differentiable Causal Discovery For Latent Hierarchical Causal Models](https://mlsanity.com/paper/2411.19556/) (2024)
- [Causal Structure and Representation Learning with Biomedical Applications](https://mlsanity.com/paper/2511.04790/) (2025)

## Abstract (arXiv)

This paper shows that causal model discovery is not an NP-hard problem, in the sense that for sparse graphs bounded by node degree k the sound and complete causal model can be obtained in worst case order N^{2(k+2)} independence tests, even when latent variables and selection bias may be present. We present a modification of the well-known FCI algorithm that implements the method for an independence oracle, and suggest improvements for sample/real-world data versions. It does not contradict any known hardness results, and does not solve an NP-hard problem: it just proves that sparse causal discovery is perhaps more complicated, but not as hard as learning minimal Bayesian networks.