Randomized algorithms are powerful tools in algorithm design, often providing simpler, faster, or more elegant solutions where deterministic methods are more complex. In this lab, we demonstrate randomness through Karger’s Min-Cut algorithm, a randomized technique for finding a minimum cut in an undirected graph.
Table of contents
Open Table of contents
Introduction
A min-cut of an undirected graph is a smallest set of edges whose removal disconnects the graph. The Karger’s Algorithm leverages randomness to efficiently find a cut with high probability of being minimum.
Unlike traditional deterministic approaches (e.g., max-flow min-cut theorem), Karger’s algorithm uses repeated random edge contraction to shrink the graph until only two vertices remain, at which point the remaining edges crossing the cut are reported.
Why randomness?
- Simpler logic
- Surprisingly strong performance with repetition
- Demonstrates probabilistic thinking in algorithm design
Karger’s Randomized Min-Cut Algorithm
Algorithm Steps
- While more than 2 vertices remain:
- Pick a random edge
- Contract it (merge endpoints into a single vertex)
- Remove self-loops
- When 2 vertices remain, the number of edges between them is a cut.
To improve accuracy, repeat the process multiple times and take the minimum cut found.
Implementation
import networkx as nx
import random
import copy
def contract_edge(graph, u, v):
for neighbor in list(graph.neighbors(v)):
if neighbor != u:
graph.add_edge(u, neighbor)
graph.remove_node(v)
return graph
def karger_min_cut(graph):
g = copy.deepcopy(graph)
while len(g.nodes) > 2:
u, v = random.choice(list(g.edges))
g = contract_edge(g, u, v)
return g.number_of_edges()
Repeating for Better Accuracy
def repeated_karger_min_cut(graph, iterations=50):
min_cut = float('inf')
for _ in range(iterations):
cut = karger_min_cut(graph)
if cut < min_cut:
min_cut = cut
return min_cut
Example Usage
Click to expand
# Create a sample graph
G = nx.complete_graph(6) # Fully connected graph
# Run the min-cut algorithm multiple times
min_cut_estimate = repeated_karger_min_cut(G, iterations=100)
print("Estimated Min-Cut:", min_cut_estimate)
Visualization
Click to expand
import matplotlib.pyplot as plt
def visualize_cut(graph, title="Original Graph"):
pos = nx.spring_layout(graph)
nx.draw(graph, pos, with_labels=True, node_color='skyblue', edge_color='gray')
plt.title(title)
plt.show()
G = nx.cycle_graph(8)
visualize_cut(G, "Cycle Graph for Min-Cut Demo")
Time and Space Complexity
| Process | Complexity |
|---|---|
| Single Run | \(O(n^2)\) |
| Repeated Trials (r) | \(O(r \cdot n^2)\) |
Where:
- \(n\) is the number of vertices
- \(r\) is the number of repetitions
The probability of finding the actual min-cut increases with the number of iterations: \(O(1/n^2)\) per trial.
Applications
- Network Reliability: Find weak points in communication networks.
- Clustering: Use cuts to partition graphs for unsupervised learning.
- Parallel Processing: Identify bottlenecks in process/task flow.
- Circuit Design: Analyze connectivity and potential faults.
Conclusion
Karger’s algorithm highlights how randomness can simplify solutions to hard problems. Although probabilistic, repeating the algorithm improves reliability. Understanding such randomized techniques is crucial for tackling large-scale, intractable graph problems in the real world.