A graphical model is a probabilistic model that uses a graph to represent conditional independence relations among random variables. We study acyclic directed graphical models, where a directed acyclic graph (DAG) is used to represent both conditional independence and causal relationships. Multiple DAGs can represent the same set of conditional independence relations; such DAGs are called Markov equivalent and belong to the same equivalence class, called a Markov equivalence class (MEC), which is graphically represented by the union of the DAGs it contains. Many combinatorial problems related to MECs have been studied in the literature. One such problem is: given the graphical representation of an MEC, compute its size. In a generalization of this problem, we are also given background knowledge in the form of a set of directed edges. A DAG in the MEC is consistent with the background knowledge if the background knowledge is a subset of its directed edges, and the goal is to count such DAGs. Another important problem is: given an undirected graph, count the number of MECs whose skeleton is the same as the undirected graph.

 

Wienöbst et al. show that counting background knowledge-consistent DAGs in an MEC is #P-hard. In this talk, we present an FPT algorithm for this problem, along with an FPT algorithm for counting MECs with a given skeleton. We further provide a faster FPT algorithm when the input graph is chordal, and a polynomial-time algorithm when the input graph is a tree.