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

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

## Key facts

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

## Builds on (most cited first, 12 of 12)

- [Learning Bayesian Networks: The Combination of Knowledge and Statistical Data](https://mlsanity.com/paper/1302.6815/) (2013)
- [Causal Inference and Causal Explanation with Background Knowledge](https://mlsanity.com/paper/1302.4972/) (2013)
- [Learning Equivalence Classes of Bayesian Networks Structures](https://mlsanity.com/paper/1302.3566/) (2013)
- [Learning Causal Graphs with Small Interventions](https://mlsanity.com/paper/1511.00041/) (2015)
- [Budgeted Experiment Design for Causal Structure Learning](https://mlsanity.com/paper/1709.03625/) (2017)
- [Active Structure Learning of Causal DAGs via Directed Clique Tree](https://mlsanity.com/paper/2011.00641/) (2020)
- [An Algorithm for Deciding if a Set of Observed Independencies Has a Causal Explanation](https://mlsanity.com/paper/1303.5435/) (2013)
- [Separators and Adjustment Sets in Causal Graphs: Complete Criteria and an Algorithmic Framework](https://mlsanity.com/paper/1803.00116/) (2018)
- [Polynomial-Time Algorithms for Counting and Sampling Markov Equivalent DAGs](https://mlsanity.com/paper/2012.09679/) (2020)
- [LazyIter: A Fast Algorithm for Counting Markov Equivalent DAGs and Designing Experiments](https://mlsanity.com/paper/2006.09670/) (2020)
- [Counting and Sampling from Markov Equivalent DAGs Using Clique Trees](https://mlsanity.com/paper/1802.01239/) (2018)
- [Formulas for Counting the Sizes of Markov Equivalence Classes of Directed Acyclic Graphs](https://mlsanity.com/paper/1610.07921/) (2016)

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

- [A Unified Experiment Design Approach for Cyclic and Acyclic Causal Models](https://mlsanity.com/paper/2205.10083/) (2022)
- [Sample Efficient Bayesian Learning of Causal Graphs from Interventions](https://mlsanity.com/paper/2410.20089/) (2024)
- [Near-Optimal Experiment Design in Linear non-Gaussian Cyclic Models](https://mlsanity.com/paper/2509.21423/) (2025)
- [New metrics and search algorithms for weighted causal DAGs](https://mlsanity.com/paper/2305.04445/) (2023)
- [Practical Algorithms for Orientations of Partially Directed Graphical Models](https://mlsanity.com/paper/2302.14386/) (2023)
- [Lower Bounds on the Size of Markov Equivalence Classes](https://mlsanity.com/paper/2506.20933/) (2025)
- [Fast Causal Orientation Learning in Directed Acyclic Graphs](https://mlsanity.com/paper/2205.13919/) (2022)
- [Counting Markov Equivalent Directed Acyclic Graphs Consistent with Background Knowledge](https://mlsanity.com/paper/2206.06744/) (2022)
- [Design of Experiment for Discovering Directed Mixed Graph](https://mlsanity.com/paper/2509.01887/) (2025)

## 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.