Let G = (V, E) be a (not necessarily simple) undirected edge-weighted graph with nonnegative weights. A cut C of G is any nontrivial subset of V, and the weight of the cut is the sum of weights of edges crossing the cut. A mincut is then defined as a cut of G of minimum weight. The problem is polynomial time solvable as a series of network flow problems or using the algorithm of Stoer and Wagner.

Boolean function | cut | maxcut | minimum vertex cut | network flow | weighted graph