Perspective

In this chapter, we have considered algorithms for solving the topological-sorting, transitive-closure, and shortest-paths 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. Worst-case 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–transitive-closure 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 worst-case preprocessing costs are significantly higher than V2, 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. Worst-case cost of digraph-processing operations

This table summarizes the cost (worst-case running time) of algorithms for various digraph-processing 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 adjacency-list representation; for the adjacency-matrix representation the E entries become V2 entries, so, for example, the cost of computing all shortest path is V3. The linear-time 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

 

single-source 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 union-find 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 mincost-flow problem, a problem-solving 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 digraph-processing 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 DFS-based 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 NP-hard. 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 mincost-flow problem and is therefore tractable. Directed Hamilton path Find the longest simple directed path in a digraph. This problem is NP-hard, 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 NP-hard 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 NP-hard. 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 digraph-processing 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.

Java graphics ltr.gif 19.145 Draw the dominator tree of the digraph Java graphics 225equ01.gif


•• 19.146 Write a class that uses DFS to create a parent-link representation of the dominator tree of a given digraph (see reference section).

Screenshot 19.147 Find a transitive reduction of the digraph Java graphics 225equ02.gif


• 19.148 Find a subgraph of the digraph Java graphics 225equ02.gif


that has the same transitive closure and the smallest number of edges among all such subgraphs.

Screenshot 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 worst-case running time proportional to VE.

Find the largest uniconnected subgraph in the digraph Java graphics 226equ01.gif


Java graphics ltr.gif 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 strong-connectivity queries take constant time, in the worst case.

Screenshot 19.154 Solve Exercise 19.153 in such a way that edge insertion, edge removal, and strong-connectivity 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 strong-connectivity queries all take near-constant time (as they do for the union-find algorithms for connectivity in undirected graphs).

Screenshot


   
Comments