Talks and Poster Presentations (with Proceedings-Entry):
R. Ganian, T. Hamm, T. Talvitie:
"An Efficient Algorithm for Counting Markov Equivalent DAGs";
Talk: 34th AAAI Conference on Artificial Intelligence (AAAI-20),
New York, New York, USA;
2020-02-07
- 2020-02-12; in: "The Thirty-Fourth AAAI Conference on Artificial Intelligence",
AAAI Press,
34
(2020),
ISSN: 2159-5399;
10136
- 10143.
English abstract:
We consider the problem of counting the number of DAGs
which are Markov-equivalent, i.e., which encode the same
conditional independencies between random variables. The
problem has been studied, among others, in the context of
causal discovery, and it is known that it reduces to counting
the number of so-called moral acyclic orientations of certain
undirected graphs, notably chordal graphs.
Our main empirical contribution is a new algorithm which
outperforms previously known exact algorithms for the considered
problem by a significant margin. On the theoretical
side, we show that our algorithm is guaranteed to run in polynomial
time on a broad class of chordal graphs, including interval
graphs.
"Official" electronic version of the publication (accessed through its Digital Object Identifier - DOI)
http://dx.doi.org/10.1609/aaai.v34i06.6573
Electronic version of the publication:
https://publik.tuwien.ac.at/files/publik_293759.pdf
Created from the Publication Database of the Vienna University of Technology.