Polynomial-Time Algorithms for Counting and Sampling Markov Equivalent DAGs with Applications
Marcel Wienöbst, Max Bannach, Maciej Liśkiewicz; 24(213):1−45, 2023.
Abstract
Counting and sampling directed acyclic graphs from a Markov equivalence class are essential tasks in graphical causal analysis. This paper presents polynomial-time algorithms that solve these tasks, addressing a long-standing problem in this field. The algorithms are practical and easy to implement. Experimental results demonstrate the feasibility of strategies in active learning of causal structures and causal effect identification within a Markov equivalence class, which were previously considered infeasible.
[abs]
[code]