Polynomial-Time Algorithms for Counting and Sampling Markov Equivalent DAGs

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. Experimental results show that the algorithms significantly outperform state-of-the-art methods.

Authors

• Marcel Wienöbst University of Lübeck
• Max Bannach Universität zu Lübeck
• Maciej Liskiewicz Universität zu Lübeck

Keywords

No keywords are indexed for this paper.