# Finding unique topological ordering wrt to another vertex ordering

Given a directed acyclic graph with $n$ nodes labeled from $1$ to $n$, what is an efficient way to produce the unique topological ordering with lower labeled nodes prioritized over higher labeled?

In other words: in the ordering the node labeled $1$ appears as early as possible, and if there are many such orders, among them choose the order(s) where the node labeled $2$ appears as early as possible, and so on producing the unique order in the end.

I tried to apply Kahn's algorithm. Instead of picking nodes arbitrary, choose ancestors of node $1$ from nodes with in-degree zero. Among those, choose ancestors of node 2, and so on. However, I don't know whether this idea can be efficiently implemented.

Choosing the lowest labeled node does not work: a counterexample is the DAG with the nodes 1, 2, 3 and 4, and edges 3 -> 1, 2 -> 4 and 4 -> 1. If we choose the lowest-numbered node, we get the ordering (2,3,1,4) but the ordering we look for is (3,1,2,4).

• What are the constraints on your running time? Does this algorithm have to run in $O(|V|+|E|)$? – Discrete lizard Apr 24 '18 at 17:49
• @Discretelizard Not necessarily in $O(|V|+|E|)$. A logarithmic factor is allowed for example but anything quadratic is too slow. – eLibrarian Apr 24 '18 at 18:11