Overview
Karger's Min Cut is a randomized graph algorithms method for global minimum cut. It works by randomly contracting edges until only two supernodes remain.
ExtendedSource checked
Karger's Min Cut
Karger's Min Cut addresses global minimum cut by randomly contracting edges until only two supernodes remain.
Quick Facts
Compact metadata for implementation and discovery.
- Category
- Graph Traversal
- Difficulty
- Intermediate
- Family
- Randomized Graph Algorithms
- Tier
- Extended
- Status
- Verified
- Review
- Source Checked
- Sources
- 2
- Formulas
- 0
- Relationships
- 3
- Code example
- Ready
- Visualization
- Ready
Core Concepts
global minimum cutrandomized graph algorithmsrandom samplinggraph traversal
Quick facts
Complexity
Runtime and memory behavior at a glance.
Best
O(V + E)
Average
O((V + E) log V)
Worst
O(V^2 + E)
Space
O(V + E)
When to Use
- Use Karger's Min Cut when solving global minimum cut and you want to benefit from randomly contracting edges until only two supernodes remain.
- Choose it when O((V + E) log V) average/worst-case time and O(V + E) memory match your workload profile.
- Prefer it over Push-Relabel or Capacity Scaling Max Flow when the problem structure favors global minimum cut.
When Not to Use
- Avoid when the graph model does not match the method's direction, weight, or connectivity assumptions.
- Avoid when a simpler traversal gives the same information with less bookkeeping.
What It Does
- Computes global minimum cut within Randomized Graph Algorithms workloads (O((V + E) log V) time, O(V + E) space).
- Works by randomly contracting edges until only two supernodes remain.
- Maintains key invariants across global minimum cut, randomized graph algorithms, random sampling.
Use Cases
- Production and research workloads requiring global minimum cut via randomly contracting edges until only two supernodes remain.
- Randomized Graph Algorithms pipelines where O((V + E) log V) time and O(V + E) space fit system constraints.
- Engineering comparisons against Push-Relabel and Capacity Scaling Max Flow when tuning global minimum cut.
Inputs
- Connected undirected multigraph G = (V, E)
- PRNG state and repetition count
Outputs
- Candidate minimum cut partition produced by random edge contractions
Pseudocode
- 1.Construct the graph representation G = (V, E) and initialize auxiliary structures for global minimum cut (randomized graph algorithms).
- 2.Seed the initial frontier, partition, or residual capacities according to Karger's Min Cut's invariants.
- 3.Iteratively process vertices or edges by randomly contracting edges until only two supernodes remain.
- 4.Maintain structural invariants (global minimum cut, randomized graph algorithms, random sampling) and prune or contract resolved subproblems.
- 5.Extract and return the final global minimum cut structure from the converged graph state.
Canonical Example
- Input
- Connected undirected multigraph G = (V, E) configured for a representative global minimum cut test case
- Output
- Candidate minimum cut partition produced by random edge contractions satisfying Karger's Min Cut invariants
- Explanation
- Karger's Min Cut processes the input by randomly contracting edges until only two supernodes remain, tracking global minimum cut and randomized graph algorithms to produce the verified global minimum cut result.
Implementation Notes
- Represent vertices and edges explicitly before optimizing storage.
- Keep graph direction, weights, and multiedges clear in tests.
- Record tie-breaking when multiple valid outputs exist.
Common Pitfalls
- Using the method on the wrong graph type, such as directed versus undirected or weighted versus unweighted.
- Forgetting disconnected components or isolated vertices.
- Letting tie-breaking hide nondeterministic output in tests.
Interactive Mechanism Walkthrough
Graph Frontier & Edge RelaxationShow randomly contracting edges until only two supernodes remain on a small global minimum cut example.
Step 1 of 5: Construct the graph representation G = (V, E) and initialize auxiliary structures for global minimum cut (randomized graph algorithms).
graph-traversal-mechanismNotes
Karger's Min Cut operates in O((V + E) log V) time and O(V + E) space within the Randomized Graph Algorithms family. Often compared with Push-Relabel and Capacity Scaling Max Flow.
Sources (2)
What each reference supports for this entry.
Network Flows: Theory, Algorithms, and Applications
BookReference for Karger's Min Cut's network-flow, cut, residual-network, or matching formulation.
Introduction to Algorithms (CLRS)
BookTextbook support for Karger's Min Cut's algorithm family, complexity framing, and standard implementation concepts.
Open sourceExplore Next
Good next jumps from the relationship graph, ranked for useful discovery.
Alternative toPush-Relabel
Graph Traversal · Core
Karger's Min Cut and Push-Relabel are practical alternatives within global minimum cut, with different assumptions and tradeoffs.
Compare with thisRelationships
View full relationship pageAlternative toPush-Relabel
Karger's Min Cut and Push-Relabel are practical alternatives within global minimum cut, with different assumptions and tradeoffs.
Alternative toCapacity Scaling Max Flow
Karger's Min Cut and Capacity Scaling Max Flow are practical alternatives within global minimum cut, with different assumptions and tradeoffs.
Alternative toGomory-Hu Tree
Karger's Min Cut and Gomory-Hu Tree are practical alternatives within global minimum cut, with different assumptions and tradeoffs.
Related Algorithms
Tags
GraphTraversalRandomness