mlsanityData to 14 Oct 2026

Polynomial-Time Algorithms for Counting and Sampling Markov Equivalent DAGs

arXiv 2012.09679 ↗First posted 17 Dec 2020cs.LG cs.AI stat.MLcited by 14

Not on the map. Why?

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.

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

Builds on

No reference list yet.

Built on by

Cited by year

Citing papers per year: 2021: 1; 2022: 4; 2023: 4; 2024: 1; 2025: 4.

14 papers.

Sort: