Counting acyclic orderings in directed acyclic graphs

Abstract

An acyclic ordering of a directed acyclic graph (DAG) $G$ is a sequence $\alpha$ of the vertices of $G$ with the property that if $i<j$, then there is a path in $G$ from $\alpha (i)$ to $\alpha (j)$. In this paper, we explore the problem of finding the number of possible acyclic orderings of a general DAG. The main result is a method for reducing a general DAG to a simpler one when counting the number of acyclic orderings. Along the way, we develop a formula for quickly obtaining this count when a DAG is a tree.