Enumerating topological sorts of a vertex-labeled DAG

Question

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.

Answer 1

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.

Answer 2

Using Kahn's algorithm, we can easily keep track of unvisited vertices at each step for the node at topological order $k\in[1..n]$. Using backtracking we can effectively accomplish this.

The worst case is a graph with no edges. In this case there are $n!$ topological orderings, and given that each contains $n$ nodes we are already at $n*n!$ output size which puts a minimum complexity. We assume we are not reusing the buffer during enumeration and must provide the enumerated items at $n$ cost such as copying an array. The unvisited nodes at all stages can worst case also be $n*(n-1)...1=n!$. So we get a worst case complexity of $(m+n)*n!$. This is a logical upper bound given that Kahn's algorithm is $O(m+n)$ and there are at most $n!$ topological sorts. Of course the polynomial time delay here has been reduced by using backtracking. In practice we will go through far less than $m*n!$ factorial edges.

One could compare the performance of enumerating with a naive method namely going through all permutations of the set $\{1..n\}$ and calling is_topological_sort. is_topological_sort is a simple algorithm which goes through all the edges of the graph and checks that topological sorting property that the edge $(x, y)$ has its topological sort index of $t_x<t_y$. Such an algorithm also has complexity $(m+n)*n!$.

The average case complexity will be of course much better not using a naive method. To prove it you would have to consider all DAGs and we know how many there are e.g. for size $n$: https://oeis.org/A003024. And we can consider also that we know the number of topological orderings for every DAG of a given length $n$: https://oeis.org/A011266 $a(n)=2^{n*(n-1)/2}*n!$.

Here is a short Python snippet that gives the adaptation:

def topo_khan_enum(g): #O((m+n)*n!)
  topo, S, k = [], set(), 0
  inc = {u: 0 for u in g}
  for u in g:
    for v in g[u]: inc[v] += 1
  for u in g:
    if inc[u] == 0: S.add(u)
  unprocessed = {0: set(S)}
  while len(unprocessed[k]) != 0:
    while len(S) != 0:
      u = unprocessed[k].pop(); S.remove(u); k += 1
      topo.append(u)
      for v in g[u]:
        inc[v] -= 1
        if inc[v] == 0: S.add(v)
      unprocessed[k] = set(S)
    if k < len(g): raise ValueError
    yield list(topo)
    while True:
      u = topo.pop(); k -= 1
      for v in g[u]:
        if inc[v] == 0: S.remove(v)
        inc[v] += 1
      S.add(u)
      if k == 0 or len(unprocessed[k]) != 0: break
  return ()

The original Kahn's algorithm is a bit simpler and certainly $O(m+n)$:

def topo_kahn(g):
  topo, S, k = [], [], 0
  inc = {u: 0 for u in g}
  for u in g:
    for v in g[u]: inc[v] += 1
  for u in g:
    if inc[u] == 0: S.append(u)
  while len(S) != 0:
    u = S.pop(); k += 1
    topo.append(u)
    for v in g[u]:
      inc[v] -= 1
      if inc[v] == 0: S.append(v)
  if k < len(g): raise ValueError
  return topo

No recursion is used here as it should never be with graph algorithms where more than a few hundred nodes need be considered, so it will work on graphs with large number of nodes.

Please note that there are elegant techniques to solve this such as in this paper: http://comjnl.oxfordjournals.org/content/24/1/83.full.pdf+html

It is based on the previous Knuth paper which could be found here: https://www.academia.edu/20852156/A_structured_program_to_generate_all_topological_sorting_arrangements

Both of these techniques should in theory be even faster albeit more complicated to implement.