mlsanityData to 7 Oct 2026

Polynomial-Time Algorithms for Counting and Sampling Markov Equivalent DAGs with Applications

arXiv 2205.02654 ↗First posted 5 May 2022cs.LG cs.AI stat.MLcited by 9

Not on the map. Why?

Abstract (arXiv)

Counting and sampling directed acyclic graphs from a Markov equivalence class are fundamental tasks in graphical causal analysis. In this paper we show that these tasks can be performed in polynomial time, solving a long-standing open problem in this area. Our algorithms are effective and easily implementable. As we show in experiments, these breakthroughs make thought-to-be-infeasible strategies in active learning of causal structures and causal effect identification with regard to a Markov equivalence class practically applicable.

Key facts. Cited by 9 papers in the map (data through 7 Oct 2026). Builds on 12 of its 59 references that are in the map. First posted on arXiv 5 May 2022.

Builds on

12 of 59 references.

References · 12

  1. 2013Learning Bayesian Networks: The Combination of Knowledge and Statistical Datacited by 185
  2. 2013Causal Inference and Causal Explanation with Background Knowledgecited by 168
  3. 2013Learning Equivalence Classes of Bayesian Networks Structurescited by 75
  4. 2015Learning Causal Graphs with Small Interventionscited by 63
  5. 2017Budgeted Experiment Design for Causal Structure Learningcited by 38
  6. 2020Active Structure Learning of Causal DAGs via Directed Clique Treecited by 38
  7. 2013An Algorithm for Deciding if a Set of Observed Independencies Has a Causal Explanationcited by 17
  8. 2018Separators and Adjustment Sets in Causal Graphs: Complete Criteria and an Algorithmic Frameworkcited by 16
  9. 2020Polynomial-Time Algorithms for Counting and Sampling Markov Equivalent DAGscited by 14
  10. 2020LazyIter: A Fast Algorithm for Counting Markov Equivalent DAGs and Designing Experimentscited by 9
  11. 2018Counting and Sampling from Markov Equivalent DAGs Using Clique Treescited by 8
  12. 2016Formulas for Counting the Sizes of Markov Equivalence Classes of Directed Acyclic Graphscited by 4

Built on by

Cited by year

Citing papers per year: 2022: 3; 2023: 2; 2024: 1; 2025: 3.

9 papers.

  1. 2022A Unified Experiment Design Approach for Cyclic and Acyclic Causal Modelscited by 7
  2. 2024Sample Efficient Bayesian Learning of Causal Graphs from Interventionscited by 4
  3. 2025Near-Optimal Experiment Design in Linear non-Gaussian Cyclic Modelscited by 4
  4. 2023New metrics and search algorithms for weighted causal DAGscited by 3
  5. 2023Practical Algorithms for Orientations of Partially Directed Graphical Modelscited by 1
  6. 2025Lower Bounds on the Size of Markov Equivalence Classescited by 1
  7. 2022Fast Causal Orientation Learning in Directed Acyclic Graphscited by 0
  8. 2022Counting Markov Equivalent Directed Acyclic Graphs Consistent with Background Knowledgecited by 0
  9. 2025Design of Experiment for Discovering Directed Mixed Graphcited by 0