Polynomial-Time Algorithms for Counting and Sampling Markov Equivalent DAGs

No. 13: AAAI-21 Technical Tracks 13

Volume

Proceedings of the AAAI Conference on Artificial Intelligence, 35

AAAI Technical Track on Reasoning under Uncertainty

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.

10.1609/aaai.v35i13.17448