The OPTNET Procedure

Minimum Cut

Subsections:

Minimum Cut for a Simple Undirected Graph

A cut is a partition of the nodes of a graph into two disjoint subsets. The cut-set is the set of links whose from and to nodes are in different subsets of the partition. A minimum cut of an undirected graph is a cut whose cut-set has the smallest link metric, which is measured as follows: For an unweighted graph, the link metric is the number of links in the cut-set. For a weighted graph, the link metric is the sum of the link weights in the cut-set.

In PROC OPTNET, you can invoke the minimum-cut algorithm by using the MINCUT statement. The options for this statement are described in the section MINCUT Statement. This algorithm can be used only on undirected graphs.

If the value of the MAXNUMCUTS= option is greater than 1, then the algorithm can return more than one set of cuts. The resulting cuts can be described in terms of partitions of the nodes of the graph or the links in the cut-sets. The node partition is specified by the mincut_i variable, for each cut i, in the data set that is specified in the OUT_NODES= option in the PROC OPTNET statement. Each node is assigned the value 0 or 1, which defines the side of the partition to which it belongs. The cut-set is defined in the output data set that is specified in the OUT= option in the MINCUT statement. This data set lists the links and their weights for each cut.

The minimum-cut algorithm reports status information in a macro variable called _OROPTNET_MINCUT_. See the section Macro Variable _OROPTNET_MINCUT_ for more information about this macro variable.

PROC OPTNET uses the Stoer-Wagner algorithm (Stoer and Wagner 1997) to compute the minimum cuts. This algorithm runs in time $O(|N||A| + |N|^2 \log |N|)$ .

Minimum Cut for a Simple Undirected Graph

As a simple example, consider the weighted undirected graph in Figure 2.42.

Figure 2.42: A Simple Undirected Graph

The links data set can be represented as follows:

data LinkSetIn;
   input from to weight @@;
   datalines;
1 2 2  1 5 3  2 3 3  2 5 2  2 6 2
3 4 4  3 7 2  4 7 2  4 8 2  5 6 3
6 7 1  7 8 3
;

The following statements calculate minimum cuts in the graph and output the results in the data set MinCut:

proc optnet
   loglevel     = moderate
   out_nodes    = NodeSetOut
   data_links   = LinkSetIn;
   mincut
     out        = MinCut
     maxnumcuts = 3;
run;
%put &_OROPTNET_;
%put &_OROPTNET_MINCUT_;

The progress of the procedure is shown in Figure 2.43.

Figure 2.43: PROC OPTNET Log for Minimum Cut

NOTE: ------------------------------------------------------------------------------------------

NOTE: Running OPTNET version 13.2.

NOTE: ------------------------------------------------------------------------------------------

NOTE: Reading the links data set.

NOTE: There were 12 observations read from the data set WORK.LINKSETIN.

NOTE: Data input used 0.01 (cpu: 0.00) seconds.

NOTE: Building the input graph storage used 0.00 (cpu: 0.00) seconds.

NOTE: The input graph storage is using 0.0 MBs of memory.

NOTE: The number of nodes in the input graph is 8.

NOTE: The number of links in the input graph is 12.

NOTE: ------------------------------------------------------------------------------------------

NOTE: Processing the minimum-cut problem.

NOTE: The minimum-cut algorithm found 3 cuts.

NOTE: The cut 1 has weight 4.

NOTE: The cut 2 has weight 5.

NOTE: The cut 3 has weight 5.

NOTE: Processing the minimum-cut problem used 0.00 (cpu: 0.00) seconds.

NOTE: ------------------------------------------------------------------------------------------

NOTE: Creating nodes data set output.

NOTE: Creating minimum-cut data set output.

NOTE: Data output used 0.00 (cpu: 0.00) seconds.

NOTE: ------------------------------------------------------------------------------------------

NOTE: The data set WORK.NODESETOUT has 8 observations and 4 variables.

NOTE: The data set WORK.MINCUT has 6 observations and 4 variables.

STATUS=OK MINCUT=OPTIMAL

STATUS=OPTIMAL OBJECTIVE=4 CPU_TIME=0.00 REAL_TIME=0.00

The data set NodeSetOut now contains the partition of the nodes for each cut, shown in Figure 2.44.

Figure 2.44: Minimum Cut Node Partition

node	mincut_1	mincut_2	mincut_3
1	1	1	1
2	1	1	0
5	1	1	0
3	0	1	0
6	1	1	0
4	0	1	0
7	0	1	0
8	0	0	0

The data set MinCut contains the links in the cut-sets for each cut. This data set is shown in Figure 2.45, which also shows each cut separately.

Figure 2.45: Minimum Cut Sets

mincut	from	to	weight
1	2	3	3
1	6	7	1
2	4	8	2
2	7	8	3
3	1	2	2
3	1	5	3

mincut=1

from	to	weight
2	3	3
6	7	1
mincut		4

mincut=2

from	to	weight
4	8	2
7	8	3
mincut		5

mincut=3

from	to	weight
1	2	2
1	5	3
mincut		5
		14