min_cut

Global minimum cut algorithms for undirected graphs.

This module finds the global minimum cut in an undirected weighted graph - the partition of nodes into two non-empty sets that minimizes the total weight of edges crossing between the sets.

Algorithm

Algorithm	Function	Complexity	Best For
Stoer-Wagner	`global_min_cut/1`	O(V³)	Dense undirected graphs

The Stoer-Wagner algorithm uses Maximum Adjacency Search (MAS) to iteratively identify minimum s-t cuts and contract nodes, similar to how Prim’s algorithm builds a minimum spanning tree but selecting by maximum edge weight.

Key Concepts

Global Min-Cut: The minimum cut over all possible partitions of the graph
s-t Cut: A cut that separates specific nodes s and t
Maximum Adjacency Search: Orders vertices by strength of connection to current set
Node Contraction: Merging two nodes while preserving edge weights

Comparison with s-t Min-Cut

For finding a cut between specific source and sink nodes, use max_flow instead:

max_flow.edmonds_karp/8 + extract_min_cut/1: O(VE²), for directed graphs
min_cut.global_min_cut/1: O(V³), for undirected graphs, finds best cut globally

Use Cases

Network reliability: Identify weakest points in communication networks
Image segmentation: Separate foreground from background in computer vision
Clustering: Graph partitioning for community detection
VLSI design: Circuit partitioning to minimize wire crossings

References

Types

MinCut

</>

pub type MinCut {
  MinCut(weight: Int, group_a_size: Int, group_b_size: Int)
}

Constructors

MinCut(weight: Int, group_a_size: Int, group_b_size: Int)

Values

global_min_cut

</>

pub fn global_min_cut(in graph: model.Graph(n, Int)) -> MinCut

Finds the global minimum cut of an undirected weighted graph using the Stoer-Wagner algorithm.

Returns the minimum cut weight and the sizes of the two partitions.

Time Complexity: O(V³)

Example

let result = min_cut.global_min_cut(in: graph)