5
\$\begingroup\$

Write a program that takes an undirected graph and finds the minimum cut, i.e., the set of edges that, if removed, would disconnect the graph into two or more connected components. The program should have a time complexity of \$O(n^2m)\$, where n is the number of vertices and m is the number of edges in the graph.

One algorithm to solve this problem is the Karger's algorithm, which is a randomized algorithm that finds the minimum cut with high probability. Here is a high-level overview of the algorithm:

  1. Initialize a "contracted graph" that is a copy of the original graph.

  2. While the contracted graph has more than 2 vertices:

    1. Choose an edge at random from the contracted graph.
    2. Contract the two vertices connected by the chosen edge into a single vertex,
    3. removing the chosen edge.
    4. Repeat steps 1 and 2 until only 2 vertices remain.
  3. The minimum cut is the set of edges that connect the two remaining vertices in the contracted graph.

This algorithm works by repeatedly contracting edges in the graph until only 2 vertices remain. The intuition behind the algorithm is that, as edges are contracted, the size of the cut decreases until there are only 2 vertices left, at which point the cut is the set of edges that connect those 2 vertices.

Karger's algorithm has a time complexity of \$O(n^2m)\$, which makes it relatively efficient for small to medium-sized graphs. However, it may not be practical for very large graphs.

\$\endgroup\$
5
  • 2
    \$\begingroup\$ Welcome to Code Golf! This site is for competitive programming challenges, so questions need to have a scoring criterion (like shortest code, or lowest complexity). You've got the restricted-complexity tag, which is a requirement for solutions, but doesn't imply any scoring method (you may want to include the fastest-algorithm winning criterion). \$\endgroup\$ Feb 14, 2023 at 14:20
  • \$\begingroup\$ thanks so much, I am adding this tag, pardon me, it is so confusing for me but thanks \$\endgroup\$
    – user116868
    Feb 14, 2023 at 14:25
  • \$\begingroup\$ You might want to check out our welcome FAQ, it goes through a lot of the important information it can be hard to figure out at first. And if you ever have any questions there's always someone active in chat! \$\endgroup\$ Feb 14, 2023 at 15:08
  • \$\begingroup\$ thanks for your friendly cooperation :) \$\endgroup\$
    – user116868
    Feb 14, 2023 at 15:15
  • 5
    \$\begingroup\$ Since minimum cut is a well studied problem in CS, this pretty much amounts to implement the fastest known algorithm, which I believe is Karger-Stein. I don't think fastest-algorithm is really a scoring criterion here. \$\endgroup\$
    – Wheat Wizard
    Feb 14, 2023 at 23:30

3 Answers 3

4
\$\begingroup\$

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.

\$\endgroup\$
2
\$\begingroup\$

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)]
\$\endgroup\$
2
  • \$\begingroup\$ do we need to show Attempt this online in such questions? \$\endgroup\$
    – user116868
    Feb 16, 2023 at 5:33
  • \$\begingroup\$ @AitzazImtiaz I assume it's encouraged, and a fastest-algorithm question usually don't suffer from impractical actual running \$\endgroup\$
    – l4m2
    Feb 16, 2023 at 16:14
0
\$\begingroup\$

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.

enter image description here

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.