Polynomial-Time Algorithms for Counting and Sampling Markov Equivalent DAGs with Applications
This breakthrough makes previously infeasible strategies in active learning of causal structures and causal effect identification practically applicable for researchers in causal inference.
The paper tackles the problem of counting and sampling directed acyclic graphs from a Markov equivalence class, showing that these tasks can be performed in polynomial time, which solves a long-standing open problem in graphical causal analysis.
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. As we show in experiments, these breakthroughs make thought-to-be-infeasible strategies in active learning of causal structures and causal effect identification with regard to a Markov equivalence class practically applicable.