Polynomial-Time Algorithms for Counting and Sampling Markov Equivalent DAGs

Marcel Wienöbst; Max Bannach; Maciej Liskiewicz

AAAI 2021technical28 citations

Polynomial-Time Algorithms for Counting and Sampling Markov Equivalent DAGs

Marcel Wienöbst, Max Bannach, Maciej Liskiewicz

Abstract

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 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.

BibTeX

@inproceedings{aaai2021_polynomialtimeal,
  title = {Polynomial-Time Algorithms for Counting and Sampling Markov Equivalent DAGs},
  author = {Marcel Wienöbst and Max Bannach and Maciej Liskiewicz},
  booktitle = {AAAI 2021},
  year = {2021}
}