论文标题
计数马尔可夫等效的定向无环图与背景知识一致
Counting Markov Equivalent Directed Acyclic Graphs Consistent with Background Knowledge
论文作者
论文摘要
Wienöbst，Bannach和Liśkiewicz（AAAI 2021）最近给出了一种用于计算Markov等效类中定向无环形图数量的多项式精确算法。在本文中，当某些边缘的方向也固定时，我们考虑了马尔可夫等效类中有针对性的无环图数量的更一般问题（例如，当介入数据部分可用时，就会出现此设置）。在较早的工作中，理论上已经表明了这个问题。相比之下，我们表明，在一个有趣的一类实例中，可以通过确定``固定参数tractable''来解决问题。特别是，我们的计数算法在及时运行，该算法在图形的大小中受多项式界定，其中多项式的程度\ emph {not}取决于提供的附加边数作为输入。
A polynomial-time exact algorithm for counting the number of directed acyclic graphs in a Markov equivalence class was recently given by Wienöbst, Bannach, and Liśkiewicz (AAAI 2021). In this paper, we consider the more general problem of counting the number of directed acyclic graphs in a Markov equivalence class when the directions of some of the edges are also fixed (this setting arises, for example, when interventional data is partially available). This problem has been shown in earlier work to be complexity-theoretically hard. In contrast, we show that the problem is nevertheless tractable in an interesting class of instances, by establishing that it is ``fixed-parameter tractable''. In particular, our counting algorithm runs in time that is bounded by a polynomial in the size of the graph, where the degree of the polynomial does \emph{not} depend upon the number of additional edges provided as input.
