Polynomial-Time Algorithms for Counting and Sampling Markov Equivalent DAGs

Marcel Wienöbst, Max Bannach, Maciej Liśkiewicz

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 thes…