Problem

Given an undirected, connected graph, find the minimum cut (the smallest set of edges whose removal disconnects the graph) using Karger’s randomized algorithm.

Example

Example 1

1
2
3

Input: Graph with 4 vertices and edges: [(0,1), (0,2), (1,2), (1,3), (2,3)]
Output: 2
Explanation: The minimum cut is 2 (removing edges (1,3) and (2,3) or (0,1) and (0,2) disconnects the graph).

Solution

Method 1 – Karger’s Randomized Contraction Algorithm

Intuition

Karger’s algorithm repeatedly contracts random edges in the graph until only two vertices remain. The number of edges between these two vertices is a candidate for the minimum cut. By running the algorithm multiple times, we can find the true minimum cut with high probability.

Approach

  • While there are more than 2 vertices:
    1. Pick a random edge (u, v).
    2. Merge (contract) u and v into a single vertex, combining their edges.
    3. Remove self-loops.
  • When only two vertices remain, the number of edges between them is a cut.
  • Repeat the process multiple times and return the smallest cut found.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

import random
from collections import defaultdict
class Solution:
    def karger_min_cut(self, edges: list[tuple[int, int]], n: int) -> int:
        def contract(edges, n):
            parent = list(range(n))
            def find(u):
                while parent[u] != u:
                    parent[u] = parent[parent[u]]
                    u = parent[u]
                return u
            curr_edges = edges[:]
            vertices = n
            while vertices > 2:
                u, v = random.choice(curr_edges)
                pu, pv = find(u), find(v)
                if pu == pv:
                    continue
                for i in range(n):
                    if parent[i] == pv:
                        parent[i] = pu
                curr_edges = [(x, y) for x, y in curr_edges if find(x) != find(y)]
                vertices -= 1
            return len(curr_edges)
        min_cut = float('inf')
        for _ in range(n * n):
            min_cut = min(min_cut, contract(edges, n))
        return min_cut

Complexity

  • ⏰ Time complexity: O(n^4), as the contraction is repeated O(n^2) times and each contraction is O(n^2).
  • 🧺 Space complexity: O(n^2), for storing edges and parent arrays.