Cut

In graph theory, a cut is a partition of the vertices of a graph into two disjoint subsets. The cut-set of the cut is the set of edges whose end points are in different subsets of the partition. Edges are said to be crossing the cut if they are in its cut-set.

In an unweighted undirected graph, the size or weight of a cut is the number of edges crossing the cut. In a weighted graph, the same term is defined by the sum of the weights of the edges crossing the cut.

In a flow network, an s-t cut is a cut that requires the source and the sink to be in different subsets, and its cut-set only consists of edges going from the source's side to the sink's side. The capacity of an s-t cut is defined by the sum of capacity of each edge in the cut-set.

The cut of a graph can sometimes refer to its cut-set instead of the partition.

Definition

A cut C = (S,T) is a partition of V of a graph G = (V, E).

An s-t cut C = (S,T) of a network N = (V, E) is a cut of N such that s∈S and t∈T, where s and t are the source and the sink of N respectively.

The cut-set of a cut C = (S,T) is the set {(u,v)∈E | u∈S, v∈T}.

Minimum cut

A cut is minimum if the size of the cut is not larger than the size of any other cut. The illustration on the right shows a minimum cut: the size of this cut is 2, and there is no cut of size 1 because the graph is bridgeless.

The max-flow-min-cut-theorem proves that the maximum network flow and the sum of the cut-edge weights of any minimum cut that separates the source and the sink are equal. There are polynomial-time methods to solve the min-cut problem, notably the Ford-Fulkerson algorithm.

Maximum cut

A cut is maximum if the size of the cut is not smaller than the size of any other cut. The illustration on the right shows a maximum cut: the size of the cut is |E| − 1 = 5, and there is no cut of size |E| because the graph is not bipartite(there is an odd cycle).

In general, finding a maximum cut is computationally hard. The max-cut problem is one of karp's 21 NP-complete problems. The max cut problem is also APX-hard, meaning that there is no polynomial-time approximation scheme (PTAS) for it unless P = NP.

Note that min-cut and max-cut are not dual problems in the linear programming sense, even though one gets from one problem to other by changing min to max in the objective function. The max-flow problem is the dual of the min-cut problem.

Sparsest cut

The Sparsest cut problem is to bipartition the vertices so as to minimize the ratio of the number of edges across the cut divided by the number of vertices in the smaller half of the partition. This objective function favors solutions that are both sparse (few edges crossing the cut) and balanced (close to a bisection), and the best known algorithm is an

approximation due to Arora, Rao and Vazirani (2004).