12
$\begingroup$

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.

$\endgroup$
-1
$\begingroup$

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.

$\endgroup$
4
  • $\begingroup$ Thanks for your answer! However, I do not understand why the tweak that you suggest in the first paragraph would be sufficient to ensure that a different topological sort label is produced after polynomially many steps. For instance, if all elements have the same label, then there is only one topological sort label to enumerate, but I am not sure I see why your algorithm would notice it and terminate sufficiently fast? (Another point: you say "neighbor", but the graph is a DAG; did you mean "child"?) $\endgroup$ – a3nm Aug 5 '16 at 15:29
  • $\begingroup$ The tweak in first para is to generate all possible orderings irrespective of labels. In order to limit the orderings in the case of similar labels, it is important to avoid selecting vertices of same labels if they seem to be similarly connected to the remaining unvisited graph. Hence, they would create isomorphic unvisited graph generating the same topological order. $\endgroup$ – sbzk Aug 6 '16 at 7:09
  • $\begingroup$ 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. $\endgroup$ – sbzk Aug 6 '16 at 7:09
  • $\begingroup$ Thanks for the explanation. However, I'm looking for a polynomial bound on the complexity which applies to all cases, not for a heuristic with no theoretical guarantees! :) $\endgroup$ – a3nm Aug 6 '16 at 9:53
-1
$\begingroup$

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.

$\endgroup$
3
  • $\begingroup$ Hi, thanks for your answer! The first paragraph is incomplete. I'm also confused about whether you are addressing the fact that I want an enumeration algorithm -- precisely because the worst case size of the output is n!. So I am not worried about bounds on the number of topological orderings. $\endgroup$ – a3nm Apr 1 at 17:26
  • $\begingroup$ I fixed the answer and provided links to the most well known papers on the algorithm implementation aspect of the topic. Yes what you are asking though is for an average case complexity or an average amortized worst case complexity. The average case must consider all DAGs while the amortized cost must find a specific DAG which causes the worst cost. The graph with n! topological sorts for example has no edges so the m factor disappears. Likely the worst case will likely a weakly connected DAG with maximal topological sorts in fact. $\endgroup$ – Gregory Morse Apr 2 at 20:03
  • $\begingroup$ Thanks for editing, but we are still not on the same page. I do not want to know about average complexity or amortized complexity. I want to know if the problem is output-polynomial, or in polynomial delay. Please refer to: en.wikipedia.org/wiki/Enumeration_algorithm. For now I'm afraid your answer is not related to what I am asking about. $\endgroup$ – a3nm Apr 3 at 18:37

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.