Title Article Swipe

PDF

Related Concepts

Chordal graph Directed acyclic graph Interval graph Indifference graph Undirected graph Combinatorics Mathematics Discrete mathematics Pathwidth Markov chain Treewidth Context (archaeology) Class (philosophy) Computer science Graph 1-planar graph Artificial intelligence Line graph Statistics Paleontology Biology

Robert Ganian , Thekla Hamm , Topi Talvitie ·

YOU? · · 2020 · Open Access · · DOI: https://doi.org/10.1609/aaai.v34i06.6573 · OA: W4236773031

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.

Keywords: Chordal graph · Directed acyclic graph · Interval graph · Indifference graph · Undirected graph · Combinatorics · Mathematics · Discrete mathematics · Pathwidth · Markov chain · Treewidth · Context (archaeology) · Class (philosophy) · Computer science · Graph · 1-planar graph · Artificial intelligence · Line graph · Statistics