3 - Minimum Cuts

Summary

In this chapter we show, as applications of maximum adjacency (MA) ordering, that a minimum cut in an edge-weighted graph can be found efficiently and that a maximum flow between certain vertices, called a pendent pair, can be computed efficiently.

There are various applications of minimum cut algorithms such as cutting plane algorithms [8, 47, 199], the traveling salesman problem (TSP) [164, 219, 311], the vehicle routing problem [15, 280], network reliability theory [176, 292, 281], large-scale circuit placement [31, 46, 114, 210], information retrieval [28], image segmentation [102], automatic graph drawing [218], compilers for parallel languages [34], and computational biology [115, 116, 124, 313].

A standard algorithm to compute a minimum cut in an edge-weighted graph G = (ν, ε) was to solve n – 1 (s, t)-maximum flow problems by changing the source sink pair (s, t) over all t ∈ ν – s, where s was fixed to an arbitrary vertex in ν. Using an O(nm log(n²/m)) time maximum flow algorithm [103] yields an O(n²m log(n²/m)) time algorithm for computing a minimum cut in G.

In Section 3.1, we show that the last two vertices in an MA ordering is a pendent pair; that is, the local edge-connectivity between them is equal to the degree of the last vertex. Using this property, in Section 3.2 we give a novel algorithm for computing a minimum cut in a graph, which runs in O(mn + n² log n) time. Section 3.3 deals with an application of the minimum-cut algorithm. In Section 3.4, we derive a hierarchical structure of MA orderings, and in Section 3.5 we see that a maximum flow between a pendent pair can be constructed in linear time.