Algorithms: Design and Analysis, Part 1 - Problem Set 4 - Question 4

Problem:

Consider our algorithm for computing a topological ordering that is based on depth-first search (i.e., NOT the "straightforward solution"). Suppose we run this algorithm on a graph G that is NOT directed acyclic. Obviously it won't compute a topological order (since none exist). Does it compute an ordering that minimizes the number of edges that go backward? For example, consider the four-node graph with the six directed edges (s,v),(s,w),(v,w),(v,t),(w,t),(t,s). Suppose the vertices are ordered s,v,w,t. Then there is one backwards arc, the (t,s) arc. No ordering of the vertices has zero backwards arcs, and some have more than one.

Solution:

Consider the following graph

0->1
1->2
2->3
3->0

If we DFS from 0, we get the topological order as 0->1->2->3, with only one backward arc (3 -> 0), which is optimal.

Consider this another graph

0->1
1->2
2->3
3->0
3->1
3->2

If we DFS from 0, we get the same topological order 0->1->2->3, with three backward arcs (3->0, 3->1, 3->2)

But if we use the order 3->0->1->2, then we only have one backward arc (2->3)

This example shows that the algorithm can sometimes minimize the number of backward arcs, but not always.