期刊
ARTIFICIAL INTELLIGENCE
卷 304, 期 -, 页码 -出版社
ELSEVIER
DOI: 10.1016/j.artint.2021.103648
关键词
Markov equivalence; Computational complexity; Chordal graphs
资金
- Austrian Science Fund (FWF) [P31336: NFPC, Y1329: ParAI]
- FWF [W1255-N23]
- University of Helsinki Research Foundation
- [P31336]
- [Y1329]
This paper addresses the problem of counting the number of Markov equivalent directed acyclic graphs (DAGs) and presents a new algorithm that outperforms previous exact algorithms. The algorithm is theoretically proven to run in polynomial time on a broad class of chordal graphs, including interval graphs.
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 cubic-time recognisable class of chordal graphs, including interval graphs. (c) 2022 Elsevier B.V. All rights reserved.
作者
我是这篇论文的作者
点击您的名字以认领此论文并将其添加到您的个人资料中。
推荐
暂无数据