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.

本文研究的问题是，在部分边缘方向已知的情况下，如何计算马尔科夫等价类中有向无环图的数量。我们发现，这个问题在一个有趣的实例类中是可固定参数可解的，因为我们建立了一个计数算法，它所需要的时间是该图大小的多项式，其次数不依赖于作为输入提供的附加边的数量。