Suppose I have a directed graph. I want to count the number of ways to label the vertices such that:
- The labels consist of the numbers 1 to n, where n is the number of vertices.
- For all edges from vertex A to B, A's label is smaller than B's label.
Is there a name for this kind of labeling? Is there a word for counting them?
This question arose from the idea of generalizing standard Young tableaux to different kinds of shapes.
Assume that the graph is acyclic; otherwise, there are no such labelings.
In this case, such a labeling is called a topological sort of the directed graph. Alternatively, if we think of the directed graph as a partial order on the vertices (with $a < b$ if there is a directed path from $a$ to $b$) then such a labeling is a linear extension of the partial order: it is a total (or linear) order $<^*$ on the vertices such that whenever $a < b$, we also have $a <^* b$.
Counting the linear extensions of a poset is #P-complete in general (the equivalent of NP-complete for a counting problem). There are many papers on approximating the number of linear extensions (usually by randomized algorithms). Any finite poset can be represented by a directed graph, so the problem of counting topological sorts of a directed graph is equivalent.
For an exact count, we can improve on the $O(n!)$ algorithm that tries all orderings: given a directed graph $G$, if $t(G)$ is the number of topological sorts of $G$, then $$ t(G) = \sum_{v : \deg^+(v) = 0} t(G - v) $$ where the sum ranges over all vertices $v$ with out-degree $0$. The rationale is that any one of those vertices (and only those vertices) can receive the label $n$, and then it remains to label the remaining vertices with $\{1,\dots,n-1\}$. If we save the result of computing $t(H)$ for each subgraph $H$ of $G$, this is an $O(n 2^n)$ algorithm.