Ph.D. Thesis in Applied Mathematics, Massachusetts Institute of Technology, July 1997. Thesis Advisor: Michel X. Goemans
The concept of connectivity plays a central role in the algorithmic aspects of network design, reliability and VLSI layout problems. A cut of an undirected graph is a bisection of its vertex set; the cut value is the number or weight of edges connecting the sides. The connectivity value is equal to the minimum cut value in the graph. In a connectivity-related problem, one typically aims to design or modify an existing graph while achieving or maintaining the connectivity value.
Several problems involving the connectivity value are known to be solvable in polynomial time: the edge augmentation problem where one wants to find an edge set of minimum total weight that increases the connectivity of a given undirected graph by T; the graph orientation problem where the edges of an undirected graph with connectivity 2k have to be oriented such that the resulting directed graph has connectivity k; the edge splitting problem where the goal is to maintain the connectivity of the input graph while isolating a prescribed vertex s by shortcutting pairs of edges us and vs adjacent to s by a new edge uv.
Polynomial time algorithms for connectivity-related problems traditionally use the max-flow min-cut theorem of Ford and Fulkerson. However, despite the massive effort to improve max-flow algorithms, computing max-flows remains a bottleneck in these problems. Recently, major steps have been made to develop non-flow based approximate and exact algorithms that find min-cuts very efficiently. While finding s-t min-cuts (min-cuts that separate a given node pair s and t) remains a relatively hard problem, it turns out that the global min-cuts (with no vertex pair specified) can be found much faster.
A main contribution of this work is the application of new cut algorithms via an approximately minimum cuts data structure. The Karger-Stein global min-cut algorithm builds an (implicit) representation of all these cuts; we demonstrate that our data structure provides an efficient query structure for the Karger-Stein algorithm. Our approximate min-cut data structure is a planar geometric representation that yields new proof techniques through geometric arguments.
Based on our cut data structure and the new randomized cut techniques, we give efficient randomized algorithms for the edge splitting, edge augmentation and graph orientation problems. In an n-vertex graph we improve the running time to solve the edge augmentation problem to ~O (n^2). In the edge splitting problem, our improved running time is ~O (n^2 max {n,d(s)/c'}) for a graph G where the total weight of edges incident to s is d(s) and c' is the minimum value of a cut distinct from the one with {s} as a cut side. Finally, we perform graph orientation in randomized ~O(n^3) time.
Our results extend the scope of randomized techniques to several applications. We do more than simply replacing an old min-cut algorithm by an improved one: our data structures enable us to substitute new global min-cut algorithms (e.g. the Karger-Stein algorithm) for one, or sometimes even O (n), of the ``hard'' s-t min-cut computations. In our results, we develop new proofs that find the optimum solutions by using our cut data structure.
Our final result applies Karger's graph sampling results to the problem of finding s-t min-cuts. We give a linear-time construction that transforms any graph on n vertices and m edges into an O(n log n)-edge graph on the same vertices whose cuts have approximately the same value as the original graph's. In this new graph, for example, we can run the ~O (mn)-time maximum flow algorithm of Goldberg and Tarjan to find an s-t minimum cut in ~O (n^2) time. This corresponds to a (1+e)-times minimum s-t cut in the original graph. In a similar way, we can approximate a sparsest cut in ~O (n^2) time.