A graphical model is a probabilistic model that uses a graph to represent conditional independence relations between random variables. We study acyclic directed graphical models, where a DAG is used to represent conditional independence relations and causal relationships between random variables. In this model, a DAG $D(V = \{v_1, v_2, \ldots, v_n\}, E)$ represents a probability distribution $P$, defined over a set of random variables $V$, if $P(v_1, v_2, \ldots, v_n) = \prod_{i}{P(v_i | \text{Parent}(v_i))}$. A node $v_i$ is said to be a parent of $v_j$ in a DAG if $v_i \rightarrow v_j$ is an edge in $G$. A DAG entails a conditional independence relation $X \perp Y \mid Z$ if all the probability distributions represented by the DAG satisfy the conditional independence relation. There can be more than one DAG that entails the same set of conditional independence relations. Such DAGs are said to be Markov equivalent. Markov equivalent DAGs 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 interesting combinatorial problems related to MECs exist in the literature. One such combinatorial problem is: Given the graphical representation of an MEC, find the size of the MEC. The problem arises from the fact that a DAG is also used as a causal graph where a directed edge $X \rightarrow Y$ implies that $X$ is a direct cause of $Y$, and the size of an MEC measures the uncertainty of the causal model when relying solely on observational data. In applications, more information about the underlying DAG than that encoded in the MEC may be available, for example due to access to some special set of interventions, or some domain-specific knowledge. Meek referred to this as \emph{background knowledge}, and modeled it as a specification of the directions of some of the edges of the underlying DAG. Wienöbst et al. show that counting such background knowledge-consistent DAGs of an MEC is \#P-hard. In this talk, we discuss an FPT algorithm for this problem. Another interesting combinatorial problem is: Given an undirected graph $G$, count the number of MECs that have the same skeleton as $G$. MECs with the same skeleton have statistical significance. In this talk, we discuss an FPT algorithm that counts MECs with the same skeleton. We also discuss an FPT algorithm that counts MECs with better time complexity than the previous algorithm when the input graph is chordal. Additionally, we discuss a polynomial algorithm to solve the problem when the input graph is a tree.