RIOT -- The Minimum and Maximum Cut Problems

The Minimum/Maximum Cut Problem

Introduction

Many optimization problems can be formulated in terms of finding that minimum (or maximum) cut in a network or graph. A cut is formed by partitioning the nodes of a graph into two mutually exclusive sets. An edge between a node in one set and a node in the other is said to be in the cut. The weight, or the capacity, of the cut is the sum of the weights of the edges that have exactly one endpoint in each of the two sets.

Minimum Cut

The problem of finding the minimum weight cut in a graph plays an important role in the design of communication networks. If a few of the links are cut or otherwise fail, the network may still be able to transmit messages between any pair of its nodes. If enough links fail, however, there will be at least one pair of nodes that cannot communicate with each other. Thus an important measure of the reliability of a network is the minimum number of links that must fail in order for this to happen. This number is referred to as the edge connectivity of the network and can be found by assigning a weight of 1 to each link and finding a minimum weight cut. In other applications, such as the open pit mining problem, we seek a minimum weight cut such that a specific pair of nodes, say node s and node t, are not in the same set. Solving this type of problem, known as a minimum s-t cut problem, is a fundamental part of the calculations used to find the baseball elimination and clinch numbers. Ahuja, Magnanti and Orlin [AMO93], present many other applications of cut problems.

Maximum Cut

This problem is the same as the minimum cut except that the capacity of the cut is maximized. Thus, we want to partition the nodes of the graph into two subsets so that the sum of the weights of the edges going from one subset to the other is maximized.

The problem of cluster analysis, partitioning a set of data points into groups of "closely related" observations, can be modeled as a maximum cut problem. The points in a particular group, or cluster, should be more "similar" or "close" to each other than they are to points in other clusters. Cluster analysis can be formulated as a maximum cut problem by creating a graph that contains a node for each data point and an edge between each pair of points. The weight of the edge is determined by the relative "closeness" of the points represented by the nodes it connects. For numerical data, for example, the relative closeness may be defined as the Euclidean distance. The clusters that are formed by finding maximum weight cuts in this graph have the property that points in one cluster are more dissimilar from points in other clusters. Barahona, Grötschel, Jünger and Reinelt [BGJR88] describe how the maximum cut problems also arises in the design of VLSI circuits and the analysis of spin-glass models.

Solving Cut Problems

Any graph has a finite number of cuts, so one could find the minimum or maximum weight cut in a graph by enumerating and comparing the size of all the cuts. This is not a practical approach for large graphs which arise in real-world applications since the number of cuts in a graph grows exponentially with the number of nodes. Fortunately, we can solve minimum cut problems without exhaustive enumeration using network flow algorithms. No such luck with the maximum weight cut: there is no known way to solve the problem optimally other than enumeration.

Rather than using enumeration to find the maximum weight cut, RIOT uses a "greedy" approximation algorithm due to Sahni and Gonzales [SG76] which is very fast and always finds a cut that has at least half the weight of the true maximum cut. For example, if you use the application to create a graph which has a maximum cut of weight 150, then RIOT will find a cut with weight 75 or higher. This type of procedure is known as an approximation algorithm since it does not always find the optimal solution, but it gives a guarantee about the quality of the solutions that it does find. In the future, RIOT will also provide an implementation of a maximum cut algorithm due to Goemans and Williamson [GW94] which finds a cut with weight at least 88% of optimal. A comprehensive treatment of approximation algorithms for a wide variety of problems can be found in "Approximation Algorithms for NP-Hard Problems", [H96] edited by Dorit S. Hochbaum.

RIOT Interactive Minimum/Maximum Cut Problem

RIOT provides an interactive problem with which you may experiment. Using a simple interface, you may construct a graph, and then let RIOT find a minimum weight or approximately maximum weight cut. To construct a network, select the number of nodes you would like, then use the mouse button to draw them on the page. Once you've laid down your nodes, draw the connections between them. The weight of the edges is set by dragging the "weight" (small black circle with a number next to it) along the edge until the desired value appears next to the weight. When you are finished defining your network, click the Submit button and wait for RIOT to solve the problem. The solution will consist of a set of GREEN nodes and a set of BLUE nodes. The minimum/maximum cut edges between the two sets will be highlighted in RED. You can submit the same graph to both the minimum and maximum cut solvers.

Note that for the maximum cut, RIOT may not give you an optimal solution. See if you can find a better solution than the cut produced by the "greedy" algorithm.

Click here to TRY IT!

References

[AMO93] R. Ahuja, T. Magnanti and J. Orlin, "Network Flows: theory, algorithms and applications," Prentice-Hall, Inc. Englewood Cliffs, New Jersey. 1993

[BGJR88] F. Barahona, M. Grötschel, M. Jünger and G. Reinelt, "An Application of Combinatorial Optimization to Statistical Physics and Circuit Layout Design," Operations Research, 3:493-513 (1988)

[GW94] M. Goemans and P. Williamson, "Improved Approximation Algorithms for Maximum Cut and Satisfiability Problems Using Semidefinite Programming," J. Assoc. Comput. Mach., (1994).

[H96] Dorit S. Hochbaum, editor. "Approximation Algorithms for NP-Hard Problems," PWS Publishing Company, Boston, MA. 1996

[SG76] S. Sahni and T. Gonzales, "P-complete approximation problems," Journal of the ACM 23:555-565. 1976

[ Maximum/Minimum Cut | Demonstration | Try It! | Instructions ]