Ingraph theory, acut is apartition of thevertices of agraph into twodisjoint subsets.[1] Any cut determines acut-set, the set of edges that have one endpoint in each subset of the partition. These edges are said tocross the cut. In aconnected graph, each cut-set determines a unique cut, and in some cases cuts are identified with their cut-sets rather than with their vertex partitions.
In aflow network, ans–t cut is a cut that requires thesource and thesink to be in different subsets, and itscut-set only consists of edges going from the source's side to the sink's side. Thecapacity of an s–t cut is defined as the sum of the capacity of each edge in thecut-set.
AcutC = (S,T) is a partition ofV of a graphG = (V,E) into two subsetsS andT.Thecut-set of a cutC = (S,T) is the set{(u,v) ∈E |u ∈S,v ∈T} of edges that have one endpoint inS and the other endpoint inT.Ifs andt are specified vertices of the graphG, then ans–t cut is a cut in whichs belongs to the setS andt belongs to the setT.
In an unweighted undirected graph, thesize orweight of a cut is the number of edges crossing the cut. In aweighted graph, thevalue orweight is defined by the sum of the weights of the edges crossing the cut.
Abond is a cut-set that does not have any other cut-set as a proper subset.
A cut isminimum if the size or weight 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 isbridgeless.
Themax-flow min-cut theorem proves that the maximumnetwork flow and the sum of the cut-edge weights of any minimum cut that separates the source and the sink are equal. There arepolynomial-time methods to solve the min-cut problem, notably theEdmonds–Karp algorithm.[2]
A cut ismaximum 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 equal to 5, and there is no cut of size 6, or |E| (the number of edges), because the graph is notbipartite (there is anodd cycle).
In general, finding a maximum cut is computationally hard.[3]The max-cut problem is one ofKarp's 21 NP-complete problems.[4]The max-cut problem is alsoAPX-hard, meaning that there is no polynomial-time approximation scheme for it unlessP = NP.[5]However, it can be approximated to within a constantapproximation ratio usingsemidefinite programming.[6]
Note that min-cut and max-cut arenotdual problems in thelinear programming sense, even though one gets from one problem to other by changing min to max in theobjective function. Themax-flow problem is the dual of themin-cut problem.[7]
Thesparsest 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). The problem is known to be NP-hard, and the best known approximation algorithm is an approximation due toArora, Rao & Vazirani (2009).[8]
The family of all cut sets of an undirected graph is known as thecut space of the graph. It forms avector space over the two-elementfinite field of arithmeticmodulo two, with thesymmetric difference of two cut sets as the vector addition operation, and is theorthogonal complement of thecycle space.[9][10] If the edges of the graph are given positive weights, the minimum weightbasis of the cut space can be described by atree on the same vertex set as the graph, called theGomory–Hu tree.[11] Each edge of this tree is associated with a bond in the original graph, and the minimum cut between two nodess andt is the minimum weight bond among the ones associated with the path froms tot in the tree.
A cut is a partition of the nodes of a graph into two sets. The cut size is the sum of the weights of the edges "between" the two sets of nodes.