# Enumerating topological sorts of a vertex-labeled DAG

Let $G = (V, E)$ be a directed acyclic graph, and let $\lambda$ be a labeling function mapping each vertex $v \in V$ to a label $\lambda(v)$ in some finite alphabet $L$. Writing $n := |V|$, a topological sort of $G$ is a bijection $\sigma$ from $\{1, \ldots, n\}$ to $V$ (i.e., an ordering of $V$ in a sequence) such that whenever $(v, v') \in E$ then $\sigma^{-1}(v) < \sigma^{-1}(v')$ (i.e., if there is an edge from $v$ to $v'$ then $v$ occurs before $v'$ in the sequence). The label of $\sigma$ is the word $\sigma(1) \cdots \sigma(n)$ in $L^n$.

Given $(G, \lambda)$, I would like to enumerate the labels of topological sorts of $G$ efficiently. What is the complexity of enumerating the labels of topological sorts? Of course, as there can be exponentially many, I want to study complexity as a function of the size of the output, or in terms of delay. In particular, can enumeration be performed with polynomial delay? (or even constant delay?)

In the case where all vertices of $G$ carry distinct labels (or, equivalently, the vertices are $\{1, \ldots, n\}$ labeled by themselves), I know that labels can be enumerated in constant amortized time, by this result on enumerating linear extensions of posets (which is the same thing as enumerating topological sorts of a DAG). However, when vertices are labeled arbitrarily, it could be the case that a very large number of topological sorts have the same label, so you can't just enumerate topological sorts of $G$ and compute their labels to get an efficient way to enumerate the labels. In poset terminology, the labeled DAG $(G, \lambda)$ can be seen as a labeled poset, and I couldn't find enumeration results about those.

I already know the hardness of some related problems thanks to answers to my other questions here. In particular, I know that finding the lexicographically minimal label is NP-hard. I also know that deciding whether a given label can be achieved by some topological sort is NP-hard (from the hardness of this problem: given a candidate label sequence $s$, ask for a topological sort of $G$ where each vertex must occur at a position where the right label occurs in $s$). However, I don't think that any of this implies hardness for enumeration, as you may enumerate in any order you like (not necessarily lexicographic), and an enumeration algorithm can't be used to decide efficiently whether a label is achievable, even with constant delay (as there may be exponentially many sequences to enumerate first).

Note that, it is obviously easy to enumerate a first label $s$ (just take any topological sort). To enumerate another label than $s$, you can proceed by imposing that some element $v$ of $V$ gets enumerated at some position $i \in \{1, \ldots, n\}$ where $s_i \neq \lambda(v)$: try out every $v$ and $i$, and check if $G$ has a topological sort where $v$ is at position $i$, which can clearly be done in PTIME. But as you output more and more labels, I'm not sure of how to generalize this approach.

One of the simplest way to compute topological ordering is performing a Depth First Search on the given DAG. Different topological orderings can be generated by exploiting the flexibility of choosing the next vertex $v$ to be traversed from the unvisited neighbours of the current vertex $u$. Since, it is a recursive procedure enumerating all possible traversals (and hence topological orders) would be simple, by choosing different orders in which unvisited neighbours of $u$ are traversed.
Now, in order to limit repeating the same traversal because of similar labels, one can compare the unvisited neighbours $v_1,v_2,...,v_k$ of $u$ having similar labels. Consider two vertices $v_i$ and $v_j$ that have the same unvisited neighbours when the traversal reaches $u$. Surely choosing either of them first would generate the same DFS tree and hence any one of them can be avoided.
Now, comparing the neighbours of all $v_1,...,v_k$ would lead to an overhead of $O(n^2)$ on the total time, but can be performed more efficiently in $\tilde{O}(n)$ by using appropriate data structures.
• For the case where all labels are same is a trivial case, otherwise even a single different label can lead to a lot of different orderings. A way to minimize computation would be to avoid processing isomorphic unvisited graphs. I do agree now that it may not guarantee an $O(n^2)$ overhead, but maybe can give a good heuristic. – sbzk Aug 6 '16 at 7:09