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

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

## Key facts

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

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

- [Causal Structure Learning: a Combinatorial Perspective](https://mlsanity.com/paper/2206.01152/) (2022)
- [Active Learning for Optimal Intervention Design in Causal Models](https://mlsanity.com/paper/2209.04744/) (2022)
- [Active causal structure learning with advice](https://mlsanity.com/paper/2305.19588/) (2023)
- [Polynomial-Time Algorithms for Counting and Sampling Markov Equivalent DAGs with Applications](https://mlsanity.com/paper/2205.02654/) (2022)
- [Do we become wiser with time? On causal equivalence with tiered background knowledge](https://mlsanity.com/paper/2306.01638/) (2023)
- [A Unified Experiment Design Approach for Cyclic and Acyclic Causal Models](https://mlsanity.com/paper/2205.10083/) (2022)
- [Efficient Enumeration of Markov Equivalent DAGs](https://mlsanity.com/paper/2301.12212/) (2023)
- [Near-Optimal Experiment Design in Linear non-Gaussian Cyclic Models](https://mlsanity.com/paper/2509.21423/) (2025)
- [Universal Lower Bound for Learning Causal DAGs with Atomic Interventions](https://mlsanity.com/paper/2111.05070/) (2021)
- [Characterization and Learning of Causal Graphs from Hard Interventions](https://mlsanity.com/paper/2505.01037/) (2025)
- [A Fixed-Parameter Tractable Algorithm for Counting Markov Equivalence Classes with the same Skeleton](https://mlsanity.com/paper/2310.04218/) (2023)
- [Less Greedy Equivalence Search](https://mlsanity.com/paper/2506.22331/) (2025)
- [Membership Testing in Markov Equivalence Classes via Independence Query Oracles](https://mlsanity.com/paper/2403.05759/) (2024)
- [Design of Experiment for Discovering Directed Mixed Graph](https://mlsanity.com/paper/2509.01887/) (2025)

## Abstract (arXiv)

Counting and uniform sampling of directed acyclic graphs (DAGs) 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. Experimental results show that the algorithms significantly outperform state-of-the-art methods.