We study the problem of counting the number of directed acyclic graphs in a Markov equivalence class (MEC) that are consistent with background knowledge specified in the form of the directions of some additional edges in the MEC. A polynomial-time algorithm for the special case of the problem, when no background knowledge constraints are specified, was given by Wienöbst, Bannach, and Liśkiewicz (AAAI 2021), who also showed that the general case is NP-hard (in fact, \#P-hard). In this talk, we show that the problem is nevertheless tractable in an interesting class of instances, by establishing that it is ``fixed-parameter tractable'' (FPT): we give an algorithm that runs in time $O(k! k^2 n^4)$, where $n$ is the number of nodes in the MEC and $k$ is the maximum number of nodes in any maximal clique of the MEC that participate in the specified background knowledge constraints. In particular, our algorithm runs in polynomial time in the well-studied special case of MECs of bounded tree-width or bounded maximum clique size.
Paper link: https://arxiv.org/abs/2206.06744
