In this chapter we study problems in directed graphs and see how the techniques developed in previous chapters generalize to problems on directed graphs. We first consider exact formulations for the arborescence problem and a vertex connectivity problem in directed graphs. For the latter, we demonstrate the iterative method in the more sophisticated uncrossing context which is applied to biset families instead of set families as in previous chapters. We then extend these results to degree bounded variants of the problems and use the iterative method to obtain bicriteria results unlike previous chapters where the algorithm would be optimal on the cost and only violate the degree constraints.

Given a directed graph D = (V, A) and a root vertex r ∈ V, a spanning r-arborescence is a subgraph of D so that there is a directed path from r to every vertex in V – r. The minimum spanning arborescence problem is to find a spanning r-arborescence with minimum total cost. We will show an integral characterization using iterative proofs, and extend this result in two directions. Given a directed graph D and a root vertex r, a rooted k-connected subgraph is a subgraph of D so that there are k internally vertex-disjoint directed paths from r to every vertex in V – r. The minimum rooted k-connected subgraph problem is to find a rooted k-connected subgraph with minimum total cost. We extend the proofs in the minimum arborescence problem to show an integral characterization in this more general setting.