Lab 06: Karger’s Min-Cut Algorithm

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.

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

1. While more than 2 vertices remain:
   • Pick a random edge
   • Contract it (merge endpoints into a single vertex)
   • Remove self-loops
2. 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

# 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

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

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

1. Network Reliability: Find weak points in communication networks.
2. Clustering: Use cuts to partition graphs for unsupervised learning.
3. Parallel Processing: Identify bottlenecks in process/task flow.
4. 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.

References

1. Karger’s Algorithm (YouTube Visual)