Karger's nondeterministic Algorithm for finding Min-Cut in graph

https://en.wikipedia.org/wiki/Karger's_algorithm

그래프에서의 Minimum Cut은 그래프의 컴포넌트를 2개로 쪼개는 데 삭제해야 하는 간선의 개수를 뜻한다. (가중치를 붙여서 일반화한 경우도 있다. 지금 소개하는 알고리즘은 그 경우는 해결하지 못하는 걸로 알고 있음)

이 중 정점 S와 T의 Minimum Cut을 구하는 것은 (즉, S와 T를 서로 다른 컴포넌트로 쪼개는 데 필요한 간선수) 알고리즘이 알려져 있다. (http://amugelab.tistory.com/entry/%EC%9C%A0%EB%9F%89-%EA%B4%80%EB%A0%A8-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%EC%A0%95%EB%A6%AC) Minimum Cut의 상한이 O(N) 이므로, O(N^3M)에 문제를 해결할 수 있으며, 사실 O(NM^2) 까지의 상한을 보장할 수 있다. (이 증명은 생략) 작동하는 가장 빠른 알고리즘은 O(NM + N^2lgN)에 동작한다.

Karger's Algorithm은 기본적으로 Contraction Algorithm이라는 알고리즘을 여러번 수행함으로써 Minimum Cut을 높은 확률로 구해내는 알고리즘이다. David Karger가 학부생 시절에 만들었다고 한다 (굇수 ㄷㄷ)

Contraction Algorithm에 대해서 설명하자면

 * 1. 아무 에지나 고른다

 * 2. 해당 에지가 잇는 두 정점을 합친다 (다시 말해서 정점 s, t를 정점 (st)로 합치고, s와 t를 잇는 간선을 삭제)

 * 3. 남은 정점의 개수가 2개 초과면 반복한다.

 * 4. 남은 정점의 개수가 2개면, 두 정점을 잇는 간선의 수가 답이다.

정점을 합치는 과정은, 에지 집합을 random shuffle한 후, union-find 자료 구조를 사용하면 O(M) 시간에 가능하다. 이 알고리즘이 답을 맞출 확률은 (1 / nC2)로 상당히 나쁘다. 때문에 Karger's Algorithm에서는 이 알고리즘을 O(N^2lgN)번 실행시킨다. (1 - 1/N^2) ^ (N^2lgN) <= 1 / N 이므로 답을 못 맞출 확률이 1 / N 정도밖에 안되기 때문이다.

고로 이 알고리즘은 1 / N 정도의 확률로 틀리고, O(N^2MlgM)에 동작한다. 하지만 조금의 변형을 가해서 이 상한을 O(N^2lg^3N) 까지 끌어올릴 수 있다고 한다.