Python, 433 bytes,

import random def karger_algorithm(graph): while len(graph) > 2: # Choose an edge at random u, v = random.choice(list(graph.items())) w = random.choice(v) # Contract the two vertices graph[u].extend(graph[w]) for node in graph[w]: graph[node].remove(w) graph[node].append(u) del graph[w] # Return the size of the cut return len(list(graph.values())[0]) # Example usage graph = {0: [1, 2], 1: [0, 2], 2: [0, 1, 3], 3: [2]} min_cut = karger_algorithm(graph) print(min_cut) 

Attempt This Online!

This implementation uses a dictionary to represent the graph, where the keys are the vertices and the values are lists of adjacent vertices. The algorithm repeatedly chooses an edge at random, contracts the two vertices connected by the edge, and updates the adjacency lists accordingly. The function returns the size of the cut, which is the number of edges that were removed.

Note that this implementation is not optimized for performance and may be slow for large graphs. There are more efficient ways to implement Karger's algorithm, such as using Union-Find data structures to keep track of connected components.

A simple implementation of Karger's algorithm in Python using union-find.

 import random def min_cut(graph): edges = [(u, v) for u, l in graph.items() for v in l if v > u] parent = {u: u for u in graph} def find(u): v = parent[u] while v != u: w = parent[v] parent[u] = w u, v = v, w return u def union(u, v): if random.randrange(2): u, v = v, u parent[u] = v random.shuffle(edges) n_components = len(graph) if n_components < 2: return None if n_components > 2: for (u, v) in edges: fu, fv = find(u), find(v) if fu != fv: union(fu, fv) n_components -= 1 if n_components == 2: break return [(u, v) for (u, v) in edges if find(u) != find(v)] 

Rust

We can use Rust to implement Karger's algorithm, one example is:

run it on Rust Playground!

extern crate rand; use rand::Rng; use std::collections::HashMap; use std::time::Instant; fn karger_algorithm(graph: &mut HashMap<u32, Vec<u32>>) -> usize { while graph.len() > 2 { // 1. Randomly select an edge in a graph let keys: Vec<_> = graph.keys().cloned().collect(); let u = rand::thread_rng().gen_range(0..keys.len()); let u_key = keys[u]; let v = rand::thread_rng().gen_range(0..graph[&u_key].len()); let w_key = graph[&u_key][v]; // 2. Contract the two vertices // Add all the neighbors of w to the Adjacency List of u, // Next, for all Adjacency Lists, w is replaced with u // Finally, delete the Adjacency List of w let w_key_values = graph[&w_key].clone(); graph.get_mut(&u_key).unwrap().extend(w_key_values.clone()); for node in w_key_values.iter() { let node_list = graph.get_mut(node).unwrap(); node_list.retain(|x| *x != w_key); node_list.push(u_key); } graph.remove(&w_key); } // 3. Return the size of the cut // Finally, there are two remaining nodes, with some edges connected between them. // Returns the number of edges graph.values().next().unwrap().len() } fn karger_algorithm_montecarlo(graph: &mut HashMap<u32, Vec<u32>>, iterations: usize) -> usize { let mut min_cut = usize::max_value(); for _ in 0..iterations { let mut graph_copy = graph.clone(); let cut = karger_algorithm(&mut graph_copy); if cut < min_cut { min_cut = cut; } } min_cut } fn main() { let mut graph: HashMap<u32, Vec<u32>> = HashMap::new(); graph.insert(0, vec![1, 2]); graph.insert(1, vec![0, 2]); graph.insert(2, vec![0, 1, 3]); graph.insert(3, vec![2]); let start = Instant::now(); let min_cut = karger_algorithm_montecarlo(&mut graph, 500); let duration = start.elapsed(); println!("Minimum cut: {}", min_cut); println!("Time elapsed: {:?}", duration); } 

Run the program with iterations=500 and find that the minimum cut can be \$1\$

-----Standard Error----- Compiling playground v0.0.1 (/playground) Finished dev [unoptimized + debuginfo] target(s) in 0.88s Running `target/debug/playground` -----Standard Output----- Minimum cut: 1 Time elapsed: 8.640442ms 

Its minimum cut is \$1\$, we can use Mathematica to verify that.