This repository contains implementations of algorithms designed to find the minimum cut in a graph. A minimum cut is the smallest set of edges that, if removed, would disconnect the graph.
karger_stein.py: Implementation of the Karger-Stein algorithm, a randomized approach to find the minimum cut in an undirected graph.stoer_wagner.py: Implementation of the Stoer-Wagner algorithm, which deterministically computes the minimum cut in an undirected graph.prove_karger_stein.py: Script to test and validate the Karger-Stein algorithm's correctness and performance.plots.py: Script to visualize the results and performance metrics of the implemented algorithms.dataset/: Directory containing sample graph datasets used for testing the algorithms.results/: Directory storing the output and visualizations generated by the algorithms.
The Karger-Stein algorithm is a randomized method that recursively contracts edges in a graph to approximate the minimum cut. While it doesn't always guarantee finding the exact minimum cut, repeating the algorithm increases the probability of success.
The Stoer-Wagner algorithm is a deterministic approach that systematically merges vertices to identify the minimum cut in an undirected graph. It guarantees finding the exact minimum cut in polynomial time.