In graph theory, a cut is a partition of the vertices of a graph into two sets. More formally, let G(V, E) denote a graph. A cut is a partition of the vertices V into two sets S and T. Any edge (u,v) ∈ E with u ∈ S and v ∈ T (or u ∈ T and v ∈ S, in case of a directed graph) is said to be crossing the cut and is a cut edge. A pictorial representation of a graph 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 partition of U into 6 blocks: a Venn diagram representation. ... In geometry, a vertex (Latin: whirl, whirlpool; plural vertices) is a corner of a polygon (where two sides meet) or of a polyhedron (where three or more faces and an equal number of edges meet). ... A pictorial representation of a graph 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. ... This article just presents the basic definitions. ...

The size of a cut is the total number of edges crossing the cut. In weighted graphs, the size of the cut is defined to be sum of weights of the edges crossing the cut. In network flow, the size of a cut is defined to be the sum of weights of the edges crossing the cut from the source side to the sink side (but not the ones that go the other way). One major problem that has plagued graph theory since its inception is the consistent lack of consistency in terminology. ... In graph theory, a network flow is an assignment of flow to the edges of a directed graph where each edge has a capacity, such that the amount of flow along an edge does not exceed its capacity. ...

Minimal and maximal cuts

A cut is minimal if the size of the cut is not larger than the size of any other cut. The max-flow min-cut theorem proves that the maximal network flow and the sum of the cut-edge weights of any minimal 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. The max-flow min-cut theorem is a statement in optimization theory about maximal flows in flow networks. ... The max-flow min-cut theorem is a statement in optimization theory about maximal flows in flow networks. ... In graph theory, a network flow is an assignment of flow to the edges of a directed graph where each edge has a capacity, such that the amount of flow along an edge does not exceed its capacity. ... In computational complexity theory, polynomial time refers to the computation time of a problem where the time, m(n), is no greater than a polynomial function of the problem size, n. ... The Ford-Fulkerson algorithm (named for L. R. Ford and D. R. Fulkerson) computes the maximum flow in a flow network. ...

A cut is maximal if the size of the cut is not smaller than the size of any other cut. Max-cut problem is one of Karp's 21 NP-complete problems. Consequently no polynomial-time algorithms for max-cut can be expected, however, various meta-heuristic search methods can efficiently produce approximate solutions. The proof of max-cut problem's NP-completeness comes by transformation from maximum 2-satisfiability (a restriction of the maximum satisfiability problem). One of the most important results of computational complexity theory was Stephen Cooks 1971 paper that demonstrated the first NP-complete problem, the boolean satisfiability problem. ... A meta-algorithm is an algorithm that can be usefully considered to have other significant algorithms, not just elementary operations and simple control structures, as its constituents; also an algorithm that has subordinate algorithms as variable and replaceable parameters. ... The introduction to this article provides insufficient context for those unfamiliar with the subject matter. ...

A polynomial-time algorithm to find maximum cuts in planar graphs exists. There is a simple 0.5-randomized approximation algorithm, which is also the best purely combinatorial algorithm for maximal cuts. The best known max-cut algorithm is an 0.878-approximation algorithm by Goemans and Williamson using semidefinite programming and randomized rounding. This algorithm yields (essentially) the best possible approximation ratio for the problem. // In graph theory, a planar graph is a graph that can be drawn (mathematicians say can be embedded in the plane) so that no edges intersect. ... Semidefinite programming (SDP) is an area of mathematics concerned with special optimization problems: the optimization of a linear objective function over the intersection of the cone of positive semidefinite matricies with an affine space. ...

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. In mathematics, linear programming (LP) problems are optimization problems in which the objective function and the constraints are all linear. ... In mathematics, linear programming (LP) problems are optimization problems in which the objective function and the constraints are all linear. ... Optimization is a branch of mathematics which is concerned with finding maxima and minima of real-valued functions. ...

See also

• Prim's algorithm
• Max-flow min-cut theorem

Prims algorithm is an algorithm in graph theory that finds a minimum spanning tree for a connected weighted graph. ... The max-flow min-cut theorem is a statement in optimization theory about maximal flows in flow networks. ...

References

• R. M. Karp, Reducibility among combinatorial problems, in R. E. Miller and J. W. Thacher (eds.), Complexity of Computer Computation, Plenum Press, New York, 85-103 (1972)
• M. X. Goemans, and D. P. Williamson, Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming, Journal of the ACM, 42, 6 (Nov. 1995), 1115-1145
• S. Khot, G. Kindler, E. Mossel, and R. O’Donnell, Optimal inapproximability results for MAX-CUT and other two-variable CSPs?, In Proceedings of the 45th IEEE Symposium on Foundations of Computer Science, pp. 146–154, 2004.
• Michael R. Garey and David S. Johnson (1979). Computers and Intractability: A Guide to the Theory of NP-Completeness. W.H. Freeman. ISBN 0-7167-1045-5.  A2.2: ND16, pg.210.