Minimum Cut Problem

Java program that uses Karger's randomized algorithm to compute the minimum cuts of an undirected, connected graph.

Input

This program takes as input a file containing the adjacency list representation of a simple, undirected, connected graph. The first column in the file represents the vertex label, and the particular row (other entries except the first column) tells all the vertices that the vertex is adjacent to.

Output

An integer representing the minimum cut i.e the fewest number of crossing edges.

How it works

The Random Contraction Algorithm invented by David Karger:

gradually contracts all vertices until there are only 2 nodes left in the graph
first, it picks uniformly at random a remaining edge (u,v)
then, it merges the two vertices into a new one, say w
removes all self loops (w,w) in the graph
the number of edges between the remaining 2 vertices denotes the number of cuts

Running time

is Big Omega(n^2 * m), where n = no of nodes and m = no of edges
can get to O(n^2) with speed-ups
although it may seem like a slow algorithm, it is actually extremely efficient compared to other approaches
however it does not always compute the minimum cut since it is a randomized algorithm and depends on which edges are contracted
we need to run the algorithm many times with different random seeds, and remember the smallest cut that we ever find

More info

Check the Coursera "Algorithms: Design and Analysis, Part 1" by professor Tim Roughgarden from Stanford University. In week 3 there is a complete proof of the probability of success (which btw is 1/n) and why this algorithm works efficiently.