# Minimum cut > Mediated Wiki article. Canonical URL: https://mediated.wiki/source/Minimum_cut > Markdown URL: https://mediated.wiki/source/Minimum_cut.md > Source: https://en.wikipedia.org/wiki/Minimum_cut > Source revision: 1343799902 > License: Creative Commons Attribution-ShareAlike 4.0 International (https://creativecommons.org/licenses/by-sa/4.0/) Partition of a graph by removing fewest possible edges A graph and two of its cuts. The dotted line in red represents a cut with three crossing edges. The dashed line in green represents one of the minimum cuts of this graph, crossing only two edges.[1] In [graph theory](/source/Graph_theory), a **minimum cut** or **min-cut** of a [graph](/source/Graph_(discrete_mathematics)) is a [cut](/source/Cut_(graph_theory)) (a [partition](/source/Partition_of_a_set) of the vertices of a graph into two disjoint subsets) that is minimal in some metric. In the simplest *unweighted min-cut problem*, the goal is to minimize the number of edges connecting the two parts. Variations of the minimum cut problem consider *weighted graphs*, *directed graphs*, *terminals*, and partitioning the vertices into *more than two sets*. The weighted min-cut problem allowing both positive and negative weights can be trivially transformed into a weighted [maximum cut](/source/Maximum_cut) problem by flipping the sign in all weights. ## Without terminal nodes The input is a graph G = (V, E). The required output is a partition V = S + T (a partition of the vertices into two disjoint subsets S and T). Any such partition has a *cost,* and the goal is to find a partition with a smallest cost. - In the unweighted version, the cost of a cut (S,T) is the number of edges with one end at S and one end at T. In this case, the minimum cut equals the [edge connectivity](/source/K-edge-connected_graph) of the graph. [Karger's algorithm](/source/Karger's_algorithm) provides an efficient randomized method for finding the cut. - In the weighted version, each edge in E has a weight, and the cost of a cut (S,T) is the total weight of edges with one end at S and one end at T. When the weights are non-negative, the problem can be solved in polynomial time by the [Stoer-Wagner algorithm](/source/Stoer-Wagner_algorithm). ### k-cut A generalization of the minimum cut problem without terminals is the [minimum k-cut](/source/Minimum_k-cut), in which the goal is to partition the graph into at least k connected components by removing as few edges as possible. For a fixed value of k, this problem can be solved in polynomial time, though the algorithm is not practical for large k. [2] ## With terminal nodes In the variant called *min s-t cut*, the input contains, in addition to the graph, two nodes called *s* (source) and *t* (target / sink). The required output is a partition V = S + T such that s is in S and t is in T. In a [flow network](/source/Flow_network), the minimum cut separates the source and sink vertices and minimizes the total sum of the capacities of the edges that are directed from the source side of the cut to the sink side of the cut. As shown in the [max-flow min-cut theorem](/source/Max-flow_min-cut_theorem), the weight of this cut equals the maximum amount of flow that can be sent from the source to the sink in the given network. In a weighted, undirected network, it is possible to calculate the cut that separates a particular pair of vertices from each other and has minimum possible total cost. A system of cuts that solves this problem for every possible vertex pair can be collected into a structure known as the [Gomory–Hu tree](/source/Gomory%E2%80%93Hu_tree) of the graph. ### k-cut A generalization of the minimum cut problem with terminals is the k-terminal cut, or multi-terminal cut. In a [planar graph](/source/Planar_graph), this problem can be solved in polynomial time. However, in general this problem is [NP-hard](/source/NP-hardness), even for k = 3 {\displaystyle k=3} .[3] ## Applications [Graph partition](/source/Graph_partition) problems are a family of combinatorial optimization problems in which a graph is to be partitioned into two or more parts with additional constraints such as balancing the sizes of the two sides of the cut. [Segmentation-based object categorization](/source/Segmentation-based_object_categorization) can be viewed as a specific case of normalized min-cut [spectral clustering](/source/Spectral_clustering) applied to [image segmentation](/source/Image_segmentation). It can also be used as a generic [clustering](/source/Cluster_analysis) method, where the nodes are data samples assumed to be taken from a [metric space](/source/Metric_space) and edge weights are their distances. This is however often impractical due do the high computational complexity for k > 2 {\displaystyle k>2} . Due to [max-flow min-cut theorem](/source/Max-flow_min-cut_theorem), 2 nodes' Minimum cut value is equal to their [maxflow](/source/Maxflow) value. In this case, some algorithms used in maxflow problem could also be used to solve this question. ## Number of minimum cuts A graph with n {\displaystyle n} vertices can at the most have ( n 2 ) = n ( n − 1 ) 2 {\displaystyle {\binom {n}{2}}={\frac {n(n-1)}{2}}} distinct minimum cuts. This bound is tight in the sense that a [(simple) cycle](/source/Cycle_(graph_theory)#Definitions) on n {\displaystyle n} vertices has exactly n ( n − 1 ) 2 {\displaystyle {\frac {n(n-1)}{2}}} minimum cuts. ## See also - [Maximum cut](/source/Maximum_cut) - [Vertex separator](/source/Vertex_separator), an analogous concept to minimum cuts for vertices instead of edges ## References 1. **[^](#cite_ref-1)** ["4 Min-Cut Algorithms"](https://web.archive.org/web/20160805175118/http://www.cs.dartmouth.edu/~ac/Teach/CS105-Winter05/Notes/loomis-scribe.ps). Archived from [the original](http://www.cs.dartmouth.edu/~ac/Teach/CS105-Winter05/Notes/loomis-scribe.ps) on 2016-08-05. 1. **[^](#cite_ref-2)** Goldschmidt, Olivier; [Hochbaum, Dorit S.](/source/Dorit_S._Hochbaum) (1994). ["A Polynomial Algorithm for the k-cut Problem for Fixed k"](https://pubsonline.informs.org/doi/pdf/10.1287/moor.19.1.24). *[Mathematics of Operations Research](/source/Mathematics_of_Operations_Research)*. **19**: 24–37. [doi](/source/Doi_(identifier)):[10.1287/moor.19.1.24](https://doi.org/10.1287%2Fmoor.19.1.24). 1. **[^](#cite_ref-3)** Dahlhaus, E.; Johnson, D. S.; Papadimitriou, C. H.; Seymour, P. D.; Yannakakis, M. (1994). ["The Complexity of Multiterminal Cuts"](https://web.archive.org/web/20181225130005/https://pdfs.semanticscholar.org/17ff/d84480267785c6a9987211a8a86a58cea1a9.pdf) (PDF). *SIAM Journal on Computing*. **23** (4): 864–894. [doi](/source/Doi_(identifier)):[10.1137/S0097539792225297](https://doi.org/10.1137%2FS0097539792225297). [S2CID](/source/S2CID_(identifier)) [1123876](https://api.semanticscholar.org/CorpusID:1123876). Archived from [the original](https://pdfs.semanticscholar.org/17ff/d84480267785c6a9987211a8a86a58cea1a9.pdf) (PDF) on 2018-12-25. Index of articles associated with the same name This [set index article](https://en.wikipedia.org/wiki/Wikipedia:Set_index_articles) includes a list of related items that share the same name (or similar names). If an [internal link](https://en.wikipedia.org/w/index.php?title=Special:Whatlinkshere/Minimum_cut&namespace=0) incorrectly led you here, you may wish to change the link to point directly to the intended article. --- Adapted from the Wikipedia article [Minimum cut](https://en.wikipedia.org/wiki/Minimum_cut) by Wikipedia contributors ([contributor history](https://en.wikipedia.org/wiki/Minimum_cut?action=history)). Available under [Creative Commons Attribution-ShareAlike 4.0 International](https://creativecommons.org/licenses/by-sa/4.0/). Changes may have been made.