Causal DAGs (also known as Bayesian networks) are a popular tool for encoding conditional dependencies between random variables. In a causal DAG, the random variables are modeled as vertices in the DAG, and it is stipulated that every random variable is independent of its non-descendants conditioned on its parents. It is possible, however, for two different causal DAGs on the same set of random variables to encode exactly the same set of conditional dependencies. Such causal DAGs are said to be Markov equivalent, and equivalence classes of Markov equivalent DAGs are known as Markov Equivalent Classes (MECs). Beautiful combinatorial characterizations of MECs have been developed in the past few decades, and it is known, in particular, that all DAGs in the same MEC must have the same skeleton (underlying undirected graph) and v-structures (induced subgraph of the form a->b

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 Liskiewicz (AAAI 2021), who also showed that the general case is NP-hard (in fact, #P-hard). In this paper, we show that the problem is nevertheless tractable in an interesting class of instances, by establishing that it is “fixed-parameter tractable”: 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.