Polynomial-Time Algorithms for Counting and Sampling Markov Equivalent DAGs
This work provides foundational algorithmic solutions for researchers and practitioners in graphical causal analysis, enabling efficient counting and sampling of equivalent causal models.
This paper presents polynomial-time algorithms for counting and uniformly sampling directed acyclic graphs (DAGs) within a Markov equivalence class. These algorithms effectively solve a long-standing open problem and significantly outperform existing state-of-the-art methods.
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.