Counting Markov Equivalent Directed Acyclic Graphs Consistent with Background Knowledge
A polynomial-time exact algorithm for counting the number of directed acyclic
graphs in a Markov equivalence class was recently given by Wien\"obst, Bannach,
and Li\'skiewicz (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.