We study a directed acyclic graphical model, also known as a Bayesian network. In this model, a directed acyclic graph (DAG) is used to represent conditional dependence between random variables. Two DAGs are said to be Markov equivalent if both represent the same set of conditional independence between the random variables. Verma and Pearl (1990) show that two DAGs are Markov equivalent if, and only if, both have the same skeleton (underlying undirected graph) and the same v-structures (induced subgraph of the form $a\rightarrow b \leftarrow c$). Markov equivalent DAGs belong to the same Markov equivalent class (MEC). A graphical representation of an MEC is the union of the DAGs it contains.
An interesting problem related to the study of MECs is: for an input undirected graph $G$, count the MECs with skeleton $G$. This problem has both graphical and statistical significance. This is a continuation of last week's talk. In last week's talk, we discussed a polynomial time algorithm that solves the problem when the skeleton is a tree graph. In this talk, we will explore a fixed parameter tractable algorithm to solve the problem. We will recall the necessary prerequisites from the previous talk.
