mlsanityData to 14 Oct 2026

Learning Sparse Causal Models is not NP-hard

arXiv 1309.6824 ↗First posted 26 Sep 2013cs.AIcited by 49

Not on the map. Why?

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.

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

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2021: 11; 2022: 6; 2023: 10; 2024: 8; 2025: 7; 2026: 7.

49 papers.

Sort:

By area:

  1. 2021A survey of Bayesian Network structure learningcited by 87
  2. 2022Causal Structure Learning: a Combinatorial Perspectivecited by 46
  3. 2023Causal Interpretation of Self-Attention in Pre-Trained Transformerscited by 30
  4. 2021Recursive Causal Structure Learning in the Presence of Latent Variables and Selection Biascited by 29
  5. 2021Iterative Causal Discovery in the Possible Presence of Latent Confounders and Selection Biascited by 21
  6. 2022Differentiable Causal Discovery Under Latent Interventionscited by 21
  7. 2022Local Constraint-Based Causal Discovery under Selection Biascited by 16
  8. 2023Causal Reasoning in the Presence of Latent Confounders via Neural ADMG Learningcited by 15
  9. 2024Causal Discovery with Fewer Conditional Independence Testscited by 13
  10. 2021Learning Bayesian Networks in the Presence of Structural Side Informationcited by 12
  11. 2023DRCFS: Doubly Robust Causal Feature Selectioncited by 12
  12. 2023Toward Falsifying Causal Graphs Using a Permutation-Based Testcited by 11
37 more
  1. 2023Generalized Independent Noise Condition for Estimating Causal Structure with Latent Variablescited by 11
  2. 2024Local Causal Structure Learning in the Presence of Latent Variablescited by 11
  3. 2022Novel Ordering-based Approaches for Causal Structure Learning in the Presence of Unobserved Variablescited by 10
  4. 2021Deconfounded Score Method: Scoring DAGs with Dense Unobserved Confoundingcited by 9
  5. 2023From Temporal to Contemporaneous Iterative Causal Discovery in the Presence of Latent Confounderscited by 9
  6. 2023Local Discovery by Partitioning: Polynomial-Time Causal Discovery Around Exposure-Outcome Pairscited by 9
  7. 2023Expert-Aided Causal Discovery of Ancestral Graphscited by 8
  8. 2021FRITL: A Hybrid Method for Causal Discovery in the Presence of Latent Confounderscited by 6
  9. 2021Improving Efficiency and Accuracy of Causal Discovery Using a Hierarchical Wrappercited by 6
  10. 2024Local Causal Discovery for Structural Evidence of Direct Discriminationcited by 6
  11. 2024A Causal World Model Underlying Next Token Prediction: Exploring GPT in a Controlled Environmentcited by 6
  12. 2021Causal Inference in medicine and in health policy, a summarycited by 4
  13. 2022CLEAR: Causal Explanations from Attention in Neural Recommenderscited by 4
  14. 2023Front-door Adjustment Beyond Markov Equivalence with Limited Graph Knowledgecited by 4
  15. 2025Embracing Discrete Search: A Reasonable Approach to Causal Structure Learningcited by 4
  16. 2023s-ID: Causal Effect Identification in a Sub-Populationcited by 3
  17. 2024Differentiable Causal Discovery For Latent Hierarchical Causal Modelscited by 3
  18. 2025Causal Structure and Representation Learning with Biomedical Applicationscited by 3
  19. 2026Score-Based Causal Discovery of Latent Variable Causal Modelscited by 3
  20. 2022Interpretability and causal discovery of the machine learning models to predict the production of CBM wells after hydraulic fracturingcited by 2
  21. 2024Generalization of LiNGAM that allows confoundingcited by 2
  22. 2025Constraint-based causal discovery with tiered background knowledge and latent variables in single or overlapping datasetscited by 2
  23. 2025Score-based Greedy Search for Structure Identification of Partially Observed Linear Causal Modelscited by 2
  24. 2021Definite Non-Ancestral Relations and Structure Learningcited by 1
  25. 2024LoSAM: Local Search in Additive Noise Models with Mixed Mechanisms and General Noise for Global Causal Discoverycited by 1
  26. 2025Causality in the human niche: lessons for machine learningcited by 1
  27. 2026On the Number of Conditional Independence Tests in Constraint-based Causal Discoverycited by 1
  28. 2021Identification of Latent Variables From Graphical Model Residualscited by 0
  29. 2021Identifiability of AMP chain graph modelscited by 0
  30. 2024Membership Testing in Markov Equivalence Classes via Independence Query Oraclescited by 0
  31. 2025Local Markov Equivalence for PC-style Local Causal Discovery and Identification of Controlled Direct Effectscited by 0
  32. 2025Causal Structure Learning in Hawkes Processes with Complex Latent Confounder Networkscited by 0
  33. 2026Efficient Causal Structure Learning via Modular Subgraph Integrationcited by 0
  34. 2026From Local to Cluster: A Unified Framework for Causal Discovery with Latent Variablescited by 0
  35. 2026A Recursive Decomposition Framework for Causal Structure Learning in the Presence of Latent Variablescited by 0
  36. 2026Characterizing and Identifying Separable Graphical Modelscited by 0
  37. 2026On the Identifiability of Mixed Ordinal and Exponential Family Causal DAGs under Linear Parametric Modelscited by 0