Given a directed graph G(V,E), with n vertices, and a parameter l>0, we
present an algorithm that finds a cut (set of edges) of small size whose
removal separates every pair of vertices (s,t) in G such that the minimum
distance between s and t in G is at least l. This theorem implies a nearly
tight analysis of the greedy algorithm for finding edge-disjoint paths in
directed graphs, and gives the best known approximation factor for this
problem in terms of the number of vertices.