# Formulas for Counting the Sizes of Markov Equivalence Classes of Directed Acyclic Graphs

arXiv: https://arxiv.org/abs/1610.07921 · HTML: https://mlsanity.com/paper/1610.07921/

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 23 Oct 2016.

## Built on by (most cited first, 4 of 4)

- [Typing assumptions improve identification in causal discovery](https://mlsanity.com/paper/2107.10703/) (2021)
- [Polynomial-Time Algorithms for Counting and Sampling Markov Equivalent DAGs with Applications](https://mlsanity.com/paper/2205.02654/) (2022)
- [Fast Causal Orientation Learning in Directed Acyclic Graphs](https://mlsanity.com/paper/2205.13919/) (2022)
- [Counting Markov Equivalent Directed Acyclic Graphs Consistent with Background Knowledge](https://mlsanity.com/paper/2206.06744/) (2022)

## Abstract (arXiv)

The sizes of Markov equivalence classes of directed acyclic graphs play important roles in measuring the uncertainty and complexity in causal learning. A Markov equivalence class can be represented by an essential graph and its undirected subgraphs determine the size of the class. In this paper, we develop a method to derive the formulas for counting the sizes of Markov equivalence classes. We first introduce a new concept of core graph. The size of a Markov equivalence class of interest is a polynomial of the number of vertices given its core graph. Then, we discuss the recursive and explicit formula of the polynomial, and provide an algorithm to derive the size formula via symbolic computation for any given core graph. The proposed size formula derivation sheds light on the relationships between the size of a Markov equivalence class and its representation graph, and makes size counting efficient, even when the essential graphs contain non-sparse undirected subgraphs.