In graph theory

Graph theory

In mathematics and computer science, graph theory is the study of graphs, mathematical structures used to model pairwise relations between objects from a certain collection. A "graph" in this context refers to a collection of vertices or 'nodes' and a collection of edges that connect pairs of...

, a minimum cut of a graph

Graph (mathematics)

In mathematics, a graph is an abstract representation of a set of objects where some pairs of the objects are connected by links. The interconnected objects are represented by mathematical abstractions called vertices, and the links that connect some pairs of vertices are called edges...

 is a cut

Cut (graph theory)

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...

 whose cutset has the smallest number of elements (unweighted case) or smallest sum of weights possible. Several algorithms exist to find minimum cuts.

For a graph G = (V, E), the problem can be reduced to 2|V| − 2 = O

Big O notation

In mathematics, big O notation is used to describe the limiting behavior of a function when the argument tends towards a particular value or infinity, usually in terms of simpler functions. It is a member of a larger family of notations that is called Landau notation, Bachmann-Landau notation, or...

(|V|) maximum flow problem

Maximum flow problem

In optimization theory, the maximum flow problem is to find a feasible flow through a single-source, single-sink flow network that is maximum....

s, equivalent to O(|V|) s − t cut problems by the max-flow min-cut theorem

Max-flow min-cut theorem

In 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 minimum capacity which when removed in a specific way from the network causes the situation that no flow can pass from the source to the...

. Hao and Orlin
have shown an algorithm to compute these max-flow problems in time asymptotically equal

Asymptotic analysis

In mathematical analysis, asymptotic analysis is a method of describing limiting behavior. The methodology has applications across science. Examples are...

 to one max-flow computation, requiring O(|V|×|E| log(|V|²/|E|)) steps.

Asymptotically faster algorithms exist for directed graphs, though these do not necessarily extend to the undirected case. A study by Chekuri et al. established experimental results with various algorithms.

Karger's algorithm

Karger's algorithm

In computer science and graph theory, the Karger's algorithm is a Monte Carlo method to compute the minimum cut of a connected graph developed by David Karger.-Algorithm:The idea of the algorithm is based on the concept of contraction of an edge e in a graph...

 is the fastest known minimum cut algorithm, is randomized, and computes a minimum cut with high probability in time O(|E| log³|V|).

Example Algorithm

Here is an example of a randomized minimum cut algorithm:

// find_min_cut(undirected graph G) {
// while there are more than 2 nodes in G do {
// pick an edge (u,v) at random in G
// contract the edge, while preserving multi-edges
// remove all loops
// }
// output the remaining edges
// }http://meami.org/mincut.html

See also

• Maximum cut
  Maximum cut
  For a graph, a maximum cut is a cut whose size is at least the size of any other cut. The problem of finding a maximum cut in a graph is known as the max-cut problem.The problem can be stated simply as follows...
  
  
• Minimum k-cut
  Minimum k-cut
  In mathematics, the minimum k-cut, is a combinatorial optimization problem that requires finding a set of edges whose removal would partition the graph to k connected components. These edges are referred to as k-cut. The goal is to find the minimum-weight k-cut...
  
  
• Graph partitioning problem
• Pseudo-Boolean function