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.

翻译：从一个Markov等值类中计算和抽样定向的单环图是图形因果分析的基本任务。在本文中,我们表明这些任务可以在多元时间内完成,从而解决这个领域长期存在的未决问题。我们的算法是有效和易于执行的。正如我们在实验中所显示的那样,这些突破使得积极学习因果结构和确定与Markov等值类相关的因果效果的思维到不可行的战略实际上适用。