Perspective
In this chapter, we have considered algorithms for solving the topologicalsorting, transitiveclosure, and shortestpaths problems for digraphs and for DAGs, including fundamental algorithms for finding cycles and strong components in digraphs. These algorithms have numerous important apps in their own right and also serve as the basis for the more difficult problems involving weighted graphs that we consider in the next two chapters. Worstcase running times of these algorithms are summarized in Table 19.3. In particular, a common theme through the chapter has been the solution of the abstract–transitiveclosure problem, where we wish to support an ADT that can determine quickly, after preprocessing, whether there is a directed path from one given vertex to another. Despite a lower bound that implies that our worstcase preprocessing costs are significantly higher than V^{2}, the method discussed in melds the basic methods from throughout the chapter into a simple solution that provides optimal performance for many types of digraphs—the significant exception being dense DAGs. The lower bound suggests that better guaranteed performance on all graphs will be difficult to achieve, but we can use these methods to get good performance on practical graphs.
Table 19.3. Worstcase cost of digraphprocessing operations
This table summarizes the cost (worstcase running time) of algorithms for various digraphprocessing problems considered in this chapter, for random graphs and graphs where edges randomly connect each vertex to one of 10 specified neighbors. All costs assume use of the adjacencylist representation; for the adjacencymatrix representation the E entries become V^{2} entries, so, for example, the cost of computing all shortest path is V^{3}. The lineartime algorithms are optimal, so the costs will reliably predict the running time on any input; the others may be overly conservative estimates of cost, so the running time may be lower for certain types of graphs. Performance characteristics of the fastest algorithms for computing the transitive closure of a digraph depend on the digraph's structure, particularly the size of its kernel DAG.


problem

cost

algorithm

digraphs


cycle detect

E

DFS


transitive closure

V(E + V)

DFS from each vertex


singlesource shortest paths

E

DFS


all shortest paths

V(E + V)

DFS from each vertex


strong components

E

Kosaraju, Tarjan, or Gabow


transitive closure

E + v(v + x)

kernel DAG

DAGs


acyclic verify

E

DFS or source queue


topological sort

E

DFS or source queue


transitive closure

V(V + E)

DFS


transitive closure

V(V + X)

DFS/dynamic programming

The goal of developing an algorithm with performance characteristics similar to the unionfind algorithms of Chapter 1 for dense digraphs remains elusive. Ideally, we would like to define an ADT where we can add directed edges or test whether one vertex is reachable from another and to develop an implementation where we can support all the operations in constant time (see Exercises 19.153 through 19.155). As discussed in Chapter 1, we can come close to that goal for undirected graphs, but comparable solutions for digraphs or DAGs are still not known. (Note that removing edges presents a challenge even for undirected graphs.) Not only does this dynamic reachability problem have both fundamental appeal and direct app in practice, but also it plays a critical role in the development of algorithms at a higher level of abstraction. For example, reachability lies at the heart of the challenge of implementing the network simplex algorithm for the mincostflow problem, a problemsolving model of wide applicability that we consider in . Many other algorithms for processing digraphs and DAGs have important practical apps and have been studied in detail, and many digraphprocessing problems still call for the development of efficient algorithms. The following list is representative. Dominators Given a DAG with all vertices reachable from a single source r, a vertex s dominates a vertex t if every path from r to t contains s. (In particular, each vertex dominates itself.) Every vertex v other than the source has an immediate dominator that dominates v but does not dominate any dominator of v but v and itself. The set of immediate dominators is a tree that spans all vertices reachable from the source. This structure is important in compiler implementations. The dominator tree can be computed in linear time with a DFSbased approach that uses several ancillary data structures, although a slightly slower version is typically used in practice. Transitive reduction Given a digraph, find a digraph that has the same transitive closure and the smallest number of edges among all such digraphs. This problem is tractable (see Exercise 19.150); but if we restrict it to insist that the result be a subgraph of the original graph, it is NPhard. Directed Euler path Given a digraph, is there a directed path connecting two given vertices that uses each edge in the digraph exactly once? This problem is easy by essentially the same argument as for the corresponding problem for undirected graphs, which we considered in (see Exercise 17.92). Directed mail carrier Given a digraph, find a directed tour with a minimal number of edges that uses every edge in the graph at least once (but is allowed to use edges multiple times). As we shall see in , this problem reduces to the mincostflow problem and is therefore tractable. Directed Hamilton path Find the longest simple directed path in a digraph. This problem is NPhard, but it is easy if the digraph is a DAG (see Exercise 19.114). Uniconnected subgraph A digraph is said to be uniconnected if there is at most one directed path between any pair of vertices. Given a digraph and an integer k, determine whether there is a uniconnected subgraph with at least k edges. This problem is known to be NPhard for general k. Feedback vertex set Decide whether a given digraph has a subset of at most k vertices that contains at least one vertex from every directed cycle in G. This problem is known to be NPhard. Even cycle Decide whether a given digraph has a cycle of even length. As mentioned in , this problem, while not intractable, is so difficult to solve that no one has yet devised an algorithm that is useful in practice. Just as for undirected graphs, myriad digraphprocessing problems have been studied, and knowing whether a problem is easy or intractable is often a challenge (see ). As indicated throughout this chapter, some of the facts that we have discovered about digraphs are expressions of more general mathematical phenomena, and many of our algorithms have applicability at levels of abstraction different from that at which we have been working. On the one hand, the concept of intractability tells us that we might encounter fundamental roadblocks in our quest for efficient algorithms that can guarantee efficient solutions to some problems. On the other hand, the classic algorithms described in this chapter are of fundamental importance and have broad applicability, as they provide efficient solutions to problems that arise frequently in practice and would otherwise be difficult to solve.
Exercises
Adapt Programs 17.18 and 17.19 to implement an ADT operation for printing an Euler path in a digraph, if one exists. Explain the purpose of any additions or changes that you need to make in the code.
19.145 Draw the dominator tree of the digraph
•• 19.146 Write a class that uses DFS to create a parentlink representation of the dominator tree of a given digraph (see reference section).
19.147 Find a transitive reduction of the digraph
• 19.148 Find a subgraph of the digraph
that has the same transitive closure and the smallest number of edges among all such subgraphs.
19.149 Prove that every DAG has a unique transitive reduction, and give an efficient method for computing the transitive reduction of a DAG.
• 19.150 Give an efficient method for computing the transitive reduction of a digraph.
Give an algorithm that determines whether or not a given digraph is uniconnected. Your algorithm should have a worstcase running time proportional to VE.
Find the largest uniconnected subgraph in the digraph
19.153 Develop a digraph class implemention that supports inserting an edge, removing an edge, and testing whether two vertices are in the same strong component, such that construction, edge insertion, and edge removal all take linear time and strongconnectivity queries take constant time, in the worst case.
19.154 Solve Exercise 19.153 in such a way that edge insertion, edge removal, and strongconnectivity queries all take time proportional to log V in the worst case.
••• 19.155 Solve Exercise 19.153 in such a way that edge insertion, edge removal, and strongconnectivity queries all take nearconstant time (as they do for the unionfind algorithms for connectivity in undirected graphs).
