graph theory In mathematics and computer science, graph theory is the study of ''graph (discrete mathematics), graphs'', which are mathematical structures used to model pairwise relations between objects. A graph in this context is made up of ''Vertex (graph ...

, a cut is a partition of the vertices of a

graph Graph may refer to: Mathematics *Graph (discrete mathematics), a structure made of vertices and edges **Graph theory, the study of such graphs and their properties *Graph (topology), a topological space resembling a graph in the sense of discret ...

into two disjoint subsets. Any cut determines a cut-set, the set of edges that have one endpoint in each subset of the partition. These edges are said to cross the cut. In a

connected graph In mathematics and computer science, connectivity is one of the basic concepts of graph theory: it asks for the minimum number of elements (nodes or edges) that need to be removed to separate the remaining nodes into two or more isolated subgrap ...

, 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 a

flow network In graph theory, a flow network (also known as a transportation network) is a directed graph where each edge has a capacity and each edge receives a flow. The amount of flow on an edge cannot exceed the capacity of the edge. Often in operations re ...

, 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 as the sum of the capacity of each edge in the ''cut-set''.

Definition

A cut is a partition of of a graph into two subsets and . The cut-set of a cut is the set of edges that have one endpoint in and the other endpoint in . If and are specified vertices of the graph , then an – cut is a cut in which belongs to the set and belongs to the 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 This is a glossary of graph theory. Graph theory is the study of graphs, systems of nodes or vertices connected in pairs by lines or edges. Symbols A B ...

, the value or weight is defined by the sum of the weights of the edges crossing the cut. A bond is a cut-set that does not have any other cut-set as a proper subset.

Minimum cut

A cut is ''minimum'' 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 is bridgeless. The

max-flow min-cut theorem In computer science and optimization theory, the max-flow min-cut theorem states that in a flow network, the maximum amount of flow passing from the ''source'' to the ''sink'' is equal to the total weight of the edges in a minimum cut, i.e., the ...

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 In theoretical computer science, the time complexity is the computational complexity that describes the amount of computer time it takes to run an algorithm. Time complexity is commonly estimated by counting the number of elementary operations p ...

methods to solve the min-cut problem, notably the Edmonds–Karp 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 equal to 5, and there is no cut of size 6, or , ''E'', (the number of edges), because the graph is not bipartite (there is an

odd cycle In graph theory, a cycle graph or circular graph is a graph that consists of a single cycle, or in other words, some number of vertices (at least 3, if the graph is simple) connected in a closed chain. The cycle graph with vertices is called ...

). 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 for it unless P = NP. However, it can be approximated to within a constant

approximation ratio In computer science and operations research, approximation algorithms are efficient algorithms that find approximate solutions to optimization problems (in particular NP-hard problems) with provable guarantees on the distance of the returned sol ...

using

semidefinite programming Semidefinite programming (SDP) is a subfield of mathematical programming concerned with the optimization of a linear objective function (a user-specified function that the user wants to minimize or maximize) over the intersection of the cone of po ...

. Note that min-cut and max-cut are ''not'' dual problems in the

linear programming Linear programming (LP), also called linear optimization, is a method to achieve the best outcome (such as maximum profit or lowest cost) in a mathematical model whose requirements and objective are represented by linear function#As a polynomia ...

sense, even though one gets from one problem to other by changing min to max in the

objective function In mathematical optimization and decision theory, a loss function or cost function (sometimes also called an error function) is a function that maps an event or values of one or more variables onto a real number intuitively representing some "cost ...

. The problem is the dual of the 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). The problem is known to be NP-hard, and the best known approximation algorithm is an

O(\sqrt)

approximation due to .

Cut space

The family of all cut sets of an undirected graph is known as the cut space of the graph. It forms a

vector space In mathematics and physics, a vector space (also called a linear space) is a set (mathematics), set whose elements, often called vector (mathematics and physics), ''vectors'', can be added together and multiplied ("scaled") by numbers called sc ...

over the two-element

finite field In mathematics, a finite field or Galois field (so-named in honor of Évariste Galois) is a field (mathematics), field that contains a finite number of Element (mathematics), elements. As with any field, a finite field is a Set (mathematics), s ...

of arithmetic

modulo In computing and mathematics, the modulo operation returns the remainder or signed remainder of a division, after one number is divided by another, the latter being called the '' modulus'' of the operation. Given two positive numbers and , mo ...

two, with the

symmetric difference In mathematics, the symmetric difference of two sets, also known as the disjunctive union and set sum, is the set of elements which are in either of the sets, but not in their intersection. For example, the symmetric difference of the sets \ and ...

of two cut sets as the vector addition operation, and is the

orthogonal complement In the mathematical fields of linear algebra and functional analysis, the orthogonal complement of a subspace W of a vector space V equipped with a bilinear form B is the set W^\perp of all vectors in V that are orthogonal to every vector in W. I ...

of the

cycle space In graph theory, a branch of mathematics, the (binary) cycle space of an undirected graph is the set of its even-degree subgraphs. This set of subgraphs can be described algebraically as a vector space over the two-element finite field. The dime ...

... If the edges of the graph are given positive weights, the minimum weight basis of the cut space can be described by a

tree In botany, a tree is a perennial plant with an elongated stem, or trunk, usually supporting branches and leaves. In some usages, the definition of a tree may be narrower, e.g., including only woody plants with secondary growth, only ...

on the same vertex set as the graph, called the Gomory–Hu tree.. Each edge of this tree is associated with a bond in the original graph, and the minimum cut between two nodes ''s'' and ''t'' is the minimum weight bond among the ones associated with the path from ''s'' to ''t'' in the tree.

References