Courses

Karger's Algorithm

Karger's Algorithm

Karger's algorithm is a randomized algorithm to compute a minimum cut (minimum number of edges) of a connected graph.  The idea of the algorithm is based on the concept of contraction of an edge (u,v) in an undirected graph G=(V,E). Informally speaking, the contraction of an edge merges the nodes u and v into one, reducing the total number of nodes of the graph by one. All other edges connecting either u or v are "reattached" to the merged node, effectively producing a multigraph. Karger's basic algorithm iteratively contracts randomly chosen edges until only two nodes remain; those nodes represent a cut in the original graph.

By iterating this basic algorithm a sufficient number of times, a minimum cut (green dashed line) can be found with high probability.

MinCut.png

Karger's algorithm in pseudocode:

Karger_Algo.png

 

TP2 - Minimum Cut

You will find the exercise uploaded at Chamilo -> Documents -> 2018 -> Week 3.

We provide some graphs in order to test your implementation of Karger's Algorithm. To start with, you can visualize the graphs using the online graphviz tool.