Contents

## Min Cut

Min Cut ๋ฌธ์ ๋, ์ด๋ค ๊ทธ๋ํ $G = (V, E)$ ๊ฐ ์ฃผ์ด์ก์ ๋, $V$์ ์ ์ ๋ค์ ๋ ์งํฉ $S, T$ ๋ก ๋๋์ด์, $$\Setcond{(u, v) \in E}{u \in S, v \in T}$$ ์ฆ, ํ์ชฝ ๋์ด $S$์, ๋ค๋ฅธ์ชฝ ๋์ด $T$์ ๋ค์ด๊ฐ๋ ๊ฐ์ ๋ค์ ๊ฐ์๋ฅผ ์ต์ํํ๋ ๋ฌธ์ ์๋๋ค. Weighted graph์์๋ ๊ฐ์ ์ ๊ฐ์๊ฐ ์๋๋ผ weight์ ํฉ์ ์ต์ํํ๋ ๋ฌธ์ ๋ก ๋ฐ๊พธ์ด ์๊ฐํ๋ฉด ๋ฉ๋๋ค.

์ฐ๋ฆฌ๋ ๋ผ์๋ฅผ ์ํด, ํธ์์ ๊ทธ๋ํ๋ฅผ unweighted connected์ ๊ฒฝ์ฐ๋ก๋ง ํ์ ํ๊ฒ ์ต๋๋ค. Directed / Undirected๋ (๊ทธ๋ฆผ์ undirected๋ก ๊ทธ๋ฆฌ๋๋ผ๋) ์ฌ์ค ๋ฌธ์  ์์ฒด๊ฐ ๋๊ฐ์ต๋๋ค. ์๊ณ ๋ฆฌ์ฆ์ ์ธก๋ฉด์์๋ ์กฐ๊ธ ์ฐจ์ด๊ฐ ์์ผ๋ฏ๋ก, ์ข๋ ์ผ๋ฐ์ ์ธ directed graph์ ๊ฒฝ์ฐ๋ฅผ ์๊ฐํ๊ฒ ์ต๋๋ค.

์๋ฅผ ๋ค์ด ์ด ๊ทธ๋ฆผ์์ ๋นจ๊ฐ์ cut์ ๊ฐ์  3๊ฐ์ง๋ฆฌ cut์ด์ง๋ง, ์ด๋ก์ cut์ ๊ฐ์  1๊ฐ์ง๋ฆฌ์๋๋ค.

## s-t min cut

Min cut ๋ฌธ์ ์ variation ์ค ํ๋๋, s-t min cut ์ด๋ผ๋ ๋ฌธ์ ์๋๋ค. ์ด ๋ฌธ์ ๋ $s, t$ ๋ผ๋ ๋ ์ ์ ์ด ๊ฐ๊ฐ $S, T$์ ์ํด์ผ ํ๋ค๋ ์ถ๊ฐ ์ ์ฝ์กฐ๊ฑด์ด ๊ฑธ๋ฆฐ min cut ๋ฌธ์ ์๋๋ค.

• ๋งค์ฐ ์ ๋ชํ Max-Flow-Min-Cut Theorem์ ์ํ๋ฉด, s-t min cut ๋ฌธ์ ๋ s-t max flow๋ก ๊ณ์ฐํ  ์ ์์ต๋๋ค. ๊ตฌ์ฒด์ ์ผ๋ก, $s$ ์์ $t$๋ก ๊ฐ๋ max flow์ $s-t$ min cut์ ํฌ๊ธฐ๊ฐ ๊ฐ๋ค๋ ์ ๋ฆฌ์๋๋ค.
• ์ด ์ ๋ฆฌ์ ํต์ฌ ์์ด๋์ด๋ ๋ ๋ฌธ์ ๋ฅผ ๊ฐ๊ฐ LP (Linear Programming) ๋ฌธ์ ๋ก ๋ฐ๊พผ ํ, ๋ LP๋ฅผ ๋น๊ตํ๋ ๊ฒ์๋๋ค. ๋ LP๋ ์๋ก primal-dual ๊ด๊ณ์ ์์์ ์ ์ ์๋๋ฐ, Dual Linear Program์ Strong duality theorem์ ์ํ๋ฉด, LP์ ๊ฒฝ์ฐ strong duality๋ฅผ ๊ฐ๊ธฐ ๋๋ฌธ์ ๋ ๋ฌธ์ ์ ์ต์ ๊ฐ, ์ฆ max-flow์ min-cut์ ๊ฒฐ๊ณผ๊ฐ์ด ๊ฐ์ต๋๋ค.
• Primal-Dual LP๋ Strong duality์ ๋ํ ์ฆ๋ช์ ์ด ํฌ์คํ์ ๋ฒ์๋ฅผ ๋์ด๊ฐ๋ ์ด์ผ๊ธฐ์ด๊ธฐ ๋๋ฌธ์ ์๋ตํฉ๋๋ค. ๊ถ๊ธํ๋ค๋ฉด 1 ์ ์ฐธ๊ณ . Farkas Lemma ๋ฑ ์์์ผ ํ  ๋ด์ฉ์ด ์๋นํ ๋ง์ต๋๋ค.
• Dinic์ ์๊ณ ๋ฆฌ์ฆ์ผ๋ก max flow๋ฅผ $O(V^2 E)$ ์ ํด๊ฒฐํ  ์ ์๊ณ , $E$ ๋ฅผ $V^2$ ๊น์ง ๊ฐ ์ ์์์ ๊ฐ์ํ๋ฉด2 ํ์ฌ ์ค์ง์ ์ผ๋ก ๊ฐ์ฅ ๋น ๋ฅธ flow๋ $O(V^3)$ ์๊ฐ์ ๋๋ ์๊ณ ๋ฆฌ์ฆ๋ค์ด ์์ต๋๋ค. (Push-Relabel with FIFO)

์ด์ , ์ผ๋ฐ์ ์ธ min cut์ ํ๊ณ ์ ํ๋ค๊ณ  ์๊ฐํด ๋ด์๋ค. ๋น์ฐํ, ๋ชจ๋  ์ ์  ํ์ด๋ฅผ $s, t$๋ก ์ก๊ณ  s-t min cut์ ํด๋ณด๋ ๋ฐฉ๋ฒ์ ์๊ฐํ  ์ ์์ผ๋ฏ๋ก, ์ฐ๋ฆฌ๋ ์ ์ด๋ $O(V^5)$ ์๊ณ ๋ฆฌ์ฆ์ ๊ฐ์ง๊ณ  ์์ต๋๋ค. ์ด๋ณด๋ค ๋์ ๋ฐฉ๋ฒ์ ์๊ฐํด ๋ด์๋ค. ์ดํ, ์๊ฐ ๋ณต์ก๋๋ฅผ ์ธ ๋ ์ ์ ์ด $n$ ๊ฐ, ๊ฐ์ ์ด $m$๊ฐ๋ผ๊ณ  ์๊ฐํ๊ฒ ์ต๋๋ค. ์ฆ $\abs{V} = n, \abs{E} = m$.

## Kargerโs Algorithm

์ง๊ธ์ MIT์ ๊ต์๋ก ๊ณ์  Prof. David R Karger๊ฐ ์ ์ํ Kargerโs Algorithm์ Edge contraction์ด๋ผ๋ ์ฐ์ฐ์ ๊ธฐ๋ฐํ๋, ๋งค์ฐ ๊ฐ๋จํ๊ณ  elegantํ ์๊ณ ๋ฆฌ์ฆ์๋๋ค.

### Edge contraction

Edge contraction์ด๋, ๋ง ๊ทธ๋๋ก edge ์์ชฝ ๋์ ์ ํฉํ๋ ์ฐ์ฐ์๋๋ค. Edge $e = (u, v)$๋ฅผ contractํ ๊ทธ๋ํ $G / e$ ๋ ๋ค์๊ณผ ๊ฐ์ ๊ณผ์ ์ ํตํด ๋ง๋ค์ด์ง๋๋ค.

• $(u, v)$ ์ ์์ชฝ vertex $u$ ๊ณผ $v$๋ฅผ ํฉ์ณ ํ๋์ vertex $w$๋ฅผ ๋ง๋ญ๋๋ค.
• $(u, x)$ ๋ $(v, x)$ ๊ฐ ์์ผ๋ฉด ์ด๊ฑธ ๋ชจ๋ $(w, x)$ ๋ก ๋ง๋ญ๋๋ค. ์ด๋, parallel edge๋ ํ์ฉ๋์ด์ผ ํฉ๋๋ค. 3
• ๊ฐ์ ๋ฐฉ๋ฒ์ผ๋ก $(x, u), (x, v)$ ์ ๋ํด์๋ ๊ฐ์ ๊ณผ์ ์ ๊ฑฐ์นฉ๋๋ค.
• ๋จ, $(u, v)$ ๊ฐ์ ์ ์ญ์ ํฉ๋๋ค. self loop์ ํ์ฉํ์ง ์๊ณ , $(w, w)$๋ ์์  ๋ฒ๋ฆฝ๋๋ค.

์๋ฅผ ๋ค์ด ์ด๋ฐ ์์๋๋ค. ๊ทธ๋ฆผ์ ๋ณด๋ฉด ๊ฑฐ์ ๋ฐ๋ก ์ดํด๊ฐ ๊ฐ๋ฏ ํฉ๋๋ค.

### Algorithm

Kargerโs Algorithm์ ์ ๋ง ์ด์ด๊ฐ ์์ ์ ๋๋ก ๊ฐ๋จํฉ๋๋ค.

• Edge Contraction์ ๊ณ์ ์งํํด์, ๋ธ๋ ๋๊ฐ์ ๊ทธ ๋ธ๋ ๋๊ฐ ์ฌ์ด์ ๊ฐ์  $k$ ๊ฐ๊ฐ ๋จ์๋ค๊ณ  ํฉ์๋ค.
• ์ฌ๋ฏธ์๋ ์ฌ์ค์, ์ฐ๋ฆฌ์ Edge contraction์ ์ฌ์ค ์ด ๋ ์ ์ ์ ๊ฐ์ ์งํฉ์ ์๋ค ๋ผ๊ณ  ์ฒ๋ฆฌํ๋ ๊ฒ๊ณผ ๋์น์๋๋ค.
• ๋ฐ๋ผ์, ๋จ์ ๋๊ฐ์ ์ ์  $a, b$์ ๋ํด a๋ก ํฉ์ณ์ง ์ ์ ์ ์งํฉ ๊ณผ b๋ก ํฉ์ณ์ง ์ ์ ์ ์งํฉ ์ $S, T$๋ก ์ผ์ผ๋ฉด, ๋ง์ง๋ง ์๊ฐ์ $a, b$๋ฅผ ์๋ $k$๊ฐ์ ๊ฐ์ ์ด cut edge๊ฐ ๋ฉ๋๋ค.
• ๊ทธ๋ฌ๋ฏ๋ก, ์ ์ ์ ๋ฌด์์  ๋๋คํ๊ฒ ์ค์ฌ๋๊ฐ๋ค๊ฐ 2๊ฐ๊ฐ ๋จ์ผ๋ฉด (min cut์ ์๋๊ฒ ์ง๋ง) cut์ ํ๋ ์ป์ต๋๋ค.
• ์ฐ๋ฆฌ๋, ์ด๊ฑธ ์ถฉ๋ถํ ๋ง์ด ๋ฐ๋ณตํ๋ฉด min cut์ ์ป์ ํ๋ฅ ์ด ์ถฉ๋ถํ ๋์์ ๋ผ์ฆํ๊ณ ์ ํฉ๋๋ค. ๊ตฌ์ฒด์ ์ผ๋ก, ์ด๋ ๊ฒ cut์ ํ๋ ์ป๋ ๊ณผ์ ๊น์ง๋ฅผ $q$ ๋ฒ ๋ฐ๋ณตํ์ฌ, ๊ทธ๋์ ์ป์ cut๋ค ์ค ๊ฐ์ฅ ์์ (๊ฐ์ ์ด ์ ์) cut์ ์ทจํ๋ ๊ฒ์ ์๊ฐํ๊ฒ ์ต๋๋ค.

### Proof

min cut์ ํฌ๊ธฐ๋ฅผ ํธ์์ $K$ ๋ผ๊ณ  ํ๊ณ , ์ค์  cut edge์ ์งํฉ์ $C$๋ผ๊ณ  ํ๊ฒ ์ต๋๋ค. ์ด์ , ์ ์๊ณ ๋ฆฌ์ฆ์ด C๋ฅผ ๋ฐํํ , ์ฆ ์ฌ๋ฐ๋ฅธ ๋ต์ ์ ๊ณตํ  ํ๋ฅ ์ $K$๊ฐ์ Edge๊ฐ $n-2$๋ฒ์ contraction์ ๋ชจ๋ ์ด์๋จ์์ผ ํฉ๋๋ค. ๊ฐ contraction์์๋ ๋จ์ edge๋ค ์ค ํ๋๋ฅผ ์์๋ก contractionํด๋ฒ๋ฆฌ๋ฏ๋ก, ๋งค ์คํ์ ๋ชจ๋ ์ด์๋จ์ ํ๋ฅ ์ $$\prod_{i = 0}^{n-3} \left(1 - \frac{K}{E - i}\right)$$ ์ด๋ ๊ฒ ๊ณ์ฐ๋ฉ๋๋ค. ๊ทธ๋ฐ๋ฐ, $\frac{K}{E - i}$ ๋ ์ ์๊ฐํด๋ณด๋ฉด ์ข์ ๋ฐ์ด๋๋ฅผ ์ก์ ์ ์์ต๋๋ค.

Contraction์ ์งํํ๋ ๊ณผ์  ์ค ํ ๋ฒ์ด๋ผ๋ ๋ง์ฝ ์ด๋ค ์ ์  $u$ ๊ฐ $d_u < K$ ๋ฅผ ๋ง์กฑํ๋ค๋ฉด, $u$ ์ ๋๋จธ์ง๋ฅผ ์๋ฅด๋ cut์ ํฌ๊ธฐ๊ฐ $d_u$ ๊ฐ ๋๊ธฐ ๋๋ฌธ์, ์ ์๋ก๋ถํฐ ๋ชจ๋  ์ ์ ์ degree๋ $K$๋ณด๋ค ์ธ์ ๋ ํฌ๊ฒ ๋ฉ๋๋ค. ๋ฐ๋ผ์ $i$๋ฒ์งธ contraction ์ด์  ๋จ์ ์ ์ ์ด $n - i$๊ฐ์ด๋ฏ๋ก ์ ์ฒด edge์ ๊ฐ์๋ $\frac{K(n-i)}{2}$ ๊ฐ๋ณด๋ค ํฌ๊ณ , ์ ํ๋ฅ  ๊ณ์ฐ์ $$p_{success} \geq \prod_{i = 0}^{n-3} \left(1 - \frac{2}{n - i}\right) = \frac{1}{\binom{n}{2}}$$ ์ด๋ ๊ฒ ๊ณ์ฐ๋๊ฒ ๋ฉ๋๋ค.

ํธํ๊ฒ, ๋์ถฉ ์ฑ๊ณต ํ๋ฅ ์ด $1 / n^2$ ์ค์ผ์ผ์ด ๋๋ค๊ณ  ํ๊ฒ ์ต๋๋ค (์ด๊ฑฐ๋ณด๋ค 2๋ฐฐ ์ข ๋๋๊ฒ ๋์ต๋๋ค). ๋ง์ฝ ์ฐ๋ฆฌ๊ฐ ์ด ์๊ณ ๋ฆฌ์ฆ์ $n^2 \log n$ ๋ฒ ์๋ํ๋ค๋ฉด, ๊ฐ๋ณ์ ์ธ ์ฑ๊ณตํ๋ฅ ์ด $1 / n^2$ ์ธ ๋ฒ ๋ฅด๋์ด ์ํ์ $n^2 \log n$ ๋ฒ ํ๋ ๊ฒ์ด๋ฏ๋ก, ๋ชจ๋ ์คํจํ  ํ๋ฅ ์ $\left(1 - \frac{1}{n^2}\right)^{n^2 \log n}$ ์ด๊ณ , ์ด ๊ฐ์ $1/n$ ๋ฏธ๋ง์๋๋ค. 4

์ด์ ๋ ์คํจํ๋ฅ ์ด๋ผ๋ฉด ์ถฉ๋ถํ ํฐ $n$์ ๋ํด์ ๋ฐ์๋ค์ผ๋ง ํฉ๋๋ค. ๋ฐ๋ผ์, ์ฐ๋ฆฌ๋ ์ด ์๊ณ ๋ฆฌ์ฆ์ $n^2 \log n$ ๋ฒ ์ ๋ ์คํํ๋ฉด ๋๋ค๊ณ  ์๊ฐํ  ์ ์์ต๋๋ค.

### Time Complexity

๊ทธ๋ํ ์๊ณ ๋ฆฌ์ฆ์ด ๋๊ฐ ๊ทธ๋ ๋ฏ ํ๋ฒ๋น ๋๋ ์๊ฐ์ ๊ตฌํํ๊ธฐ ๋๋ฆ์๋๋ค. Adjacency matrix๊ฐ ์๋ค๋ฉด $O(n^2)$ ์ผ๋ก ๊ตฌํํ๋ฉด ๋๊ณ , Adj list๊ฐ ์๋ค๋ฉด $O(m)$ ๋น์ทํ ์๊ฐ์ด ๊ฑธ๋ฆฌ๋๊ฒ ๊ทธ๋ด๋ฏํด ๋ณด์๋๋ค. ๊ฐ์ฅ ์ฝ๊ฒ ์ง๋ ๋ฐฉ๋ฒ์ Kruskal ์๊ณ ๋ฆฌ์ฆ์ ๊ตฌํํ  ๋์ฒ๋ผ ๊ตฌํํ๋ ๋ฐฉ๋ฒ์ด๊ณ , ์ด ๋ฐฉ๋ฒ์ ๊ตฌํ์ฒด๋ (์ธ์  ๊ฐ ์ ๊ฐ ๊ตฌํํ๋ฉด ๊ตฌํ์ฒด ๋งํฌ๋ฅผ ์ฌ๋ฆด ์์ ์๋๋ค) $O(m \log m)$ ์ ๋์ ๋๊ฒ ํ  ์ ์์ต๋๋ค. ์ด๋ ๊ฒ ์ง๋ฉด $m \approx n^2$ ์ผ ๋ ์ต๋ $O(n^2 \log n)$ ์ด ๋๋ฏ๋ก, ์ ์ฒด ๋ณต์ก๋๋ $O(n^4 \log^2 n)$ ์ด ๋๊ฒ ์ต๋๋ค.

๊ตฌํ์ ์ ํ๋ฉด ํ๋ฒ iteration์ $O(m)$ ์ ๋๊ฒ ํด์, $O(n^4 \log n)$ ์ ๊ตฌ๊ฒจ ๋ฃ์ ์ ์์ต๋๋ค๋ง, ์ด๊ฑด ๊ทธ๋ํ ๊ตฌํ์ ์ ํ๋์ง์ ๋ฌธ์ ์ด๋ฏ๋ก ์ฐ๋ฆฌ๋ ๋ค๋ฃจ์ง ์๊ฒ ์ต๋๋ค. ๋ค๋ง, ์๊ณ ๋ฆฌ์ฆ์ ๋ถ์์๋ ์ค์ํ๋ฏ๋ก, Karger ์๊ณ ๋ฆฌ์ฆ์ ์ ๊ตฌํํ์ ๋์ ๋ณต์ก๋๋ ํ๋ฒ Iteration์ $O(n^2)$, $n^2 \log n$ ๋ฒ ๋ฐ๋ณตํ  ๊ฒ์ด๋ฏ๋ก $O(n^4 \log n)$ ์ด๋ค ๋ผ๊ณ  ์ฐ๊ฒ ์ต๋๋ค.

## Karger-Stein Algorithm

Karger-Stein์ ์ ์๊ณ ๋ฆฌ์ฆ๊ณผ ๊ฑฐ์ ๋๊ฐ์ง๋ง, Clever idea๊ฐ ์ด์ง ์ถ๊ฐ๋์ด ํจ์ฌ ๋นจ๋ผ์ง๋๋ค. ๋ค์ ์์์ ํ๋ฅ  ๊ณ์ฐ์ผ๋ก ๋์๊ฐ๊ฒ ์ต๋๋ค. $$p_{success} \geq \prod_{i = 0}^{n-3} \left(1 - \frac{2}{n - i}\right)$$ ์ด์ , ์ฌ๊ธฐ์ ๊ด์ฐฐํ๊ณ  ์ถ์ ์ฌ์ค์, ์ด๋ฐ๋ณด๋ค ํ๋ฐ์ ์ฑ๊ณตํ๋ฅ ์ด ๋น ๋ฅด๊ฒ ๋ฎ์์ง๋ค๋ ์ ์๋๋ค. ์ฆ ์ด๋ฐ์๋ ๋ง๊ตฌ ๋ฝ์๋ ๋์ถฉ ๋ง์๊ฒ์ด๋ผ๊ณ  ๊ธฐ๋ํ  ์ ์์ง๋ง, ํ๋ฐ์๋ ์ ์  ๋ถ์ํด์ง๊ธฐ ์์ํ๋ค๋ ๊ฒ์ด์ฃ . ๋ฐ๋ผ์, ์ด๋ฐ์๋ ๋์ถฉ ๋ฝ์์ ๋ฏฟ์์ ๊ฐ์ง๊ณ  ๋๋ฆฌ๋ค๊ฐ, ํ๋ฐ์๋ ์ข ๋นก์ธ๊ฒ ๋ณด๋ฉด ์ข์ง ์์๊น์?

์ด์ ์ ์ฐฉ์ํ Karger-Stein์ ๋ธ๋ ๊ฐ์๊ฐ ๋์ถฉ $V / \sqrt{2}$๊ฐ๊ฐ ๋ ๋๊น์ง๋ ๊ทธ๋ฅ ๋ธ๋๋ฅผ Karger์ฒ๋ผ ์ค์ด๋ค๊ฐ, ๋ธ๋๊ฐ ์ ๋งํผ ๋จ์ผ๋ฉด ๋๋ฐฐ๋ก ๋ง์ด ๊ฒํ ํฉ๋๋ค. ์ด ์์น๋ฅผ ์ฐ๋ ์ด์ ๋, ๊ณ์ฐํด ๋ณด๋ฉด $V / \sqrt{2}$๊ฐ์ ๋ธ๋๊ฐ ๋จ์ ๋๊น์ง Contraction์ ํ๋ฉด ์ด๋์ min cut์ด ์ด์๋จ์ ํ๋ฅ ์ด $1/2$ ๊ฐ ์ด์ง ๋๊ธฐ ๋๋ฌธ์๋๋ค. ์ฆ, ์๋ Karger ์๊ณ ๋ฆฌ์ฆ์ $n$๊ฐ๋ถํฐ $2$๊ฐ๊น์ง ์ค์ฌ๋ณด๋๊ฑธ ํ ์คํ์ด๋ผ๊ณ  ์ ์ํ์ง๋ง, $n$ ๊ฐ๋ถํฐ $n / \sqrt{2}$ ๊ฐ๊น์ง๋ ๊ทธ๋ฅ ๋ง ์ค์ด๊ณ , $n / \sqrt{2}$ ๋ถํฐ $n / 2$ ๊ฐ๊ฐ ๋  ๋๊น์ง ์ค์ฌ๋ณด๋ ํ๋์ ๋๋ฒ ํด์ ๋์๊ฑธ ๊ณ ๋ฅด๊ณ โฆ ์ด๋ฐ ์์๋๋ค. ๋จ, ์ฌ๊ท์ ์ผ๋ก ์๋ํ๋ค๋ ์ ์ ์ฃผ์ํด์ผ ํฉ๋๋ค. Pseudocode๋ฅผ ์ฐ๋ฉด,

์ฌ๊ธฐ์ contract(G, t) ํจ์๋ $G$์ edge๊ฐ $t$๊ฐ ๋  ๋๊น์ง ๋๋คํ๊ฒ contractionํด์ ์ค์ด๋ ํจ์์๋๋ค. 6์ ๋ณ ์๋ฏธ๊ฐ ์๋ ์์๋ ์๋๊ณ , ๊ทธ๋ฅ base case๋ฅผ ์ค ๊ฒ์ผ๋ก ์๊ฐํ์๋ฉด ๋ฉ๋๋ค.

์ด ์๊ณ ๋ฆฌ์ฆ์ ์ฑ๊ณต ํ๋ฅ ๊ณผ ์คํ ์๊ฐ์ ๋ํด ์ดํดํด ๋ณด๊ฒ ์ต๋๋ค. ๋จ, ์ํคํผ๋์๋ ์ฌ๋ฌ ์๋ฃ์๋ ceil ๋ฑ์ผ๋ก ์ข ์ ํํ๊ฒ ์จ์์ง๋ง ์ฐ๋ฆฌ๋ ์ด์ฐจํผ big-O notation์ ceil์ ํ๋๋ง๋๋ ์ํฅ๋ ์๊ณ โฆ ๋์ถฉ ๋ชจ๋  ์๋ฅผ ์ ์๋ผ๊ณ  ์๊ฐํ๊ณ  ๋๊ธฐ๊ฒ ์ต๋๋ค. $n / \sqrt{2}$ ๊ฐ์๊ฑธ ๋์ถฉ ์ฐ๊ธฐ๋ก ํฉ์๋ค. (์ฌ์ค ๋ถ์์๋ ์๋ฌด ๋ฌธ์  ์์ต๋๋ค!)

### Time Complexity of iteration

ํธํ๊ฒ, Ceiling ๊ฐ์๊ฑฐ ๋ค ๋ ๋ฆฌ๊ณ  ์ ํ์์ ์จ ๋ณด๊ฒ ์ต๋๋ค. ์ Pseudocode์ fastmincut(G)๊ฐ ์ ์  $n$๊ฐ์ ๊ทธ๋ํ์ผ ๋, Contract ํ๋ฒ์ด ์ ์  ๊ฐ์๋งํผ์ ์๊ฐ์ ์๋ชจํจ์ ๊ณ ๋ คํ๋ฉด5 , $\sum_{i = n / \sqrt{2}}^{n} i$ ๋ $O(n^2)$ ์ด๋ฏ๋ก (๋์ถฉ $n^2 / 4$ ์ ๋ ๋๋ค๋๊ฑธ ๋ณด์ด๊ธฐ ๋ณ๋ก ์ด๋ ต์ง ์์ต๋๋ค),
$$T(n) = 2 T(n / \sqrt{2}) + O(n^2)$$ ์ด๋ฐ ์ ํ์์ ์ป์ต๋๋ค. ์ฐ๋ฆฌ ๋ชจ๋ ์๊ณ ๋ฆฌ์ฆ ์๊ฐ์ ์ด๋ฏธ ๋ฐฐ์ด ๋ง์คํฐ ์ ๋ฆฌ๋ฅผ ์ฐ๋ฉด, $\log_{\sqrt{2}} 2 = 2$ ์ด๋ฏ๋ก, $T(n) = O(n^2 \log n)$ ์ ์ป์ต๋๋ค. ์ฆ, ํ๋ฒ ์ฐ์ฐ์๋ $n^2 \log n$ ์๊ฐ์ด ๊ฑธ๋ฆฐ๋ค๋ ๊ฒ์๋๋ค. ์์์ Karger๊ณผ ๋น๊ตํ๋ฉด, ๋๋ฐฐ๋ก ์ฐ์ฐ์ ๋๋ฆฌ๋ ๊ณผ์ ์์ $\log n$ ๋งํผ์ ์๊ฐ์ ์ถ๊ฐ๋ก ์ง๋ถํ๋ค๋๊ฒ์ ์ ์ ์์ต๋๋ค.

### Probability of Success

์ด์  ํ๋ฒ ์๋์ ์ฑ๊ณต ํ๋ฅ ์ ๋ํด ์์์ผ ํฉ๋๋ค. $P(n)$ ์ $n$๊ฐ ์ ์ ์ ๋ํด fastmincut์ ๊ฒฐ๊ณผ๊ฐ ์ฌ๋ฐ๋ฅผ ํ๋ฅ ์ด๋ผ๊ณ  ํ๋ฉด, ์ด ํจ์๊ฐ ์คํจํ๊ธฐ ์ํด์๋ ๋ ๊ฐ์ fastmincut(n / sqrt(2)) ๊ฐ ๋ชจ๋ ์คํจํด์ผ ํฉ๋๋ค. ๋ฐ๋ผ์, ๋ค์ ์ ํ์์ ์ธ ์ ์์ต๋๋ค. $$P(n) = 1 - \left(1 - \frac{1}{2} P\left(\frac{n}{\sqrt{2}}\right)\right)^2$$

• ๋จผ์ , ๋งจ ์์ชฝ์ ๋ถ๋ 1/2 ๋, $n$๊ฐ์์ $n / \sqrt{2}$ ๋ก ์ค์ผ ๋ ๋ง๊ฒ ์ค์์ ํ๋ฅ ์ด 1/2 ๋ฐ์ ๋์ง ์๊ธฐ ๋๋ฌธ์๋๋ค. ์ฌ์ค ์ด ํ๋ฅ ์ด 1/2๋ณด๋ค ์ด์ง ํฌ๋ค๋ ๊ฒ์ ์ฆ๋ชํ  ์ ์๊ธฐ ๋๋ฌธ์ $P(n) \geq$ ๋ก ์์ํ๋ ๋ถ๋ฑ์์ผ๋ก ์ฐ๋ ๊ฒ์ด ๋ง์ต๋๋ค.
• ๊ทธ๋ค์์ ๋น์ฐํ, $P(n / \sqrt{2})$ ๋ก, ์ด ์๊ณ ๋ฆฌ์ฆ์ด ์ฌ๊ท์ ์ผ๋ก ๋ง์ ํ๋ฅ ์ ์จ ์ค๋๋ค.
• ์ฐ๋ฆฌ๋ 1 - (๋ ๋ค ์คํจํ  ํ๋ฅ ) ์ ๊ตฌํ๋ฏ๋ก, ์ด๋ ๋ค์ 1 - (ํ๋๊ฐ ์คํจํ  ํ๋ฅ )^2 ๊ฐ ๋ฉ๋๋ค. ํ๋๊ฐ ์คํจํ  ํ๋ฅ ์ 1 - (ํ๋๊ฐ ์ฑ๊ณตํ  ํ๋ฅ ) ์ด๋ฏ๋ก, ์์ ๊ฐ์ด ๊ตฌํ๋ ๊ฒ์ด ์ ๋นํฉ๋๋ค.

์ด์ , ์ด ์์ ํธ๋ ๋ฐฉ๋ฒ์ Induction์๋๋ค.

์ ์์ ์ ์ ๊ฐํ๋ฉด, $P(n) = P(n / \sqrt{2}) - \frac{1}{4} P(n / \sqrt{2})^2$ ์์ ์ ์ ์์ต๋๋ค.

์ฐ๋ฆฌ๋ ์ด์  $P(n) \geq \frac{1}{\log{n}}$ ์ ์ฃผ์ฅํฉ๋๋ค. (๋จ, ๋ก๊ทธ๋ ๋ก๊ทธ2) By induction, ๋ค์์ ์ค๋ฅธ์ชฝ ๋ถ๋ฑํธ๋ฅผ ์ฆ๋ชํ๋ฉด ์ฆ๋ช์ด ๋๋ฉ๋๋ค. $$P(n) \geq \frac{1}{\log(n/\sqrt{2})} - \frac{1}{4\log^2(n/\sqrt{2})} \geq \frac{1}{\log n}$$ ์ด ๋ถ๋ฑ์์ ์ง์  ํ๊ธฐ๋ ์กฐ๊ธ ๊ท์ฐฎ์ง๋ง, ๋ณ๋ก ์ด๋ ต์ง๋ ์์ต๋๋ค. ์์งํ, ๋ํ์ ์๊ณ ๋ฆฌ์ฆ ์์์์ ๋ฐฐ์ฐ๋ ๋ด์ฉ์ ๋ํ ๊ธ์ ์ฌ๊ธฐ๊น์ง ์ฝ์๋งํผ ํฅ๋ฏธ์ ๊ด์ฌ์ด ์๋ ์ด์ํ ์ฌ๋์ด๋ผ๋ฉด ์ ์ ๋ ๋ถ๋ฑ์์ ์ฆ๋ชํ๊ธฐ ๋ณ๋ก ์ด๋ ต์ง ์์ ๊ฒ ๊ฐ์ง๋ง, ์นผ์ ๋ค์์ผ๋ฉด ๋ฌด๋ฅผ ์ฐ์ด์ผ ํ๋ค๋ ์ฒ ํ์ ์ํด ์ค๊ฐ ์คํ์ ๋์ถฉ ์๋ตํ๋๋ผ๋ ๋์ถฉ ์ค์ผ์นํด ๋ณด๊ฒ ์ต๋๋ค.

๋ฐ์ด 2์ธ ๋ก๊ทธ๋ฅผ ์ฐ๊ณ  ์์ผ๋ฏ๋ก, ์ ์์ ์ด๋ ๊ฒ ์ ๋ฆฌ๊ฐ ๋ฉ๋๋ค. $$\frac{1}{\log n - 1/2)} - \frac{1}{4(\log n - 1/2)}$$

์ด์ , ์ด ์์ ๊พธ์ญ๊พธ์ญ ํต๋ถํด์ $$\frac{4 \log n - 3}{4\log^2 n - 4\log n + 1} = \frac{1}{\log n} + \frac{1 - 1 / \log{n}}{4\log^2 n - 4\log n + 1} \geq \frac{1}{\log n}$$

์ด๋ ๊ฒ ์ป์ต๋๋ค. ๋ถ๋ฑ์์ ๋ ์ด์๊ฒ ํจ๋ฉด $2 / \log n$ ์ธ๊ฐ? ํ๋ ๋ฐ์ด๋๋ ์ก์ ์ ์์ํ๋ฐ, ๋ณ๋ก ์ค์ํ ๋ผ์๋ ์๋๋๋ค.

์ด์จ๋ , ์ฐ๋ฆฌ๋ ํ๋ฒ ์ฑ๊ณตํ๋ฅ ์ด $1 / \log n$ ์์ค์์ ์์์ต๋๋ค.

### Total time complexity

๋ช๋ฒ ์ํํ  ๊ฒ์ธ์ง๋ง ์ ํ๋ฉด ๋์๋๋ค. ์์ Karger ์๊ณ ๋ฆฌ์ฆ์ ์๊ฐ ๋ณต์ก๋ ์ฆ๋ช์์ ํ๋ ๊ฒ๊ณผ ๋๊ฐ์ ์ฐ์ฐ์ ํด ๋ณด๋ฉด, ์ฑ๊ณตํ๋ฅ ์ด $p(n)$ ์ธ ๋ฒ ๋ฅด๋์ด ์ํ์ ๋ฐ๋ณตํด์ $1/n$ ์ดํ์ ์คํจํ๋ฅ ์ ๊ฐ๊ฒ ํ๋ ค๋ฉด, $q(n)$ ๋ฒ ์คํํ๋ค๊ณ  ํ  ๋ $$\left(1 - p(n)\right)^{q(n)} \leq 1 / n$$ ์ด ์์ ๋ชฉํ๋ก ํ๋ ๊ฒ์ธ๋ฐ, $(1 - x)^{1/x}$ ์ ๊ฐ์ด $1/e$ ์ดํ์์ ๋ค์ ์ด์ฉ ($p(n) \leq 1$์ด๋ฏ๋ก!), $q(n)$ ์ $\frac{\log n}{p(n)}$ ๋ฒ์ผ๋ก ์ก์์ฃผ๋ฉด ๋๋ค๋ ๊ฒ์ ์ ์ ์์ต๋๋ค. ๋ฐ๋ผ์, $q(n) = \log^2 n$ ์ผ๋ก ์ก์์ฃผ๋ฉด ๋ฉ๋๋ค.

์ฐ๋ฆฌ๋ ๊ฐ๋ณ ์๊ฐ์ด $O(n^2 \log n)$ ์ธ ์ํ์ $\log^2 n$๋ฒ ์ํํ๊ธฐ๋ก ๊ฒฐ์ ํ์ผ๋ฏ๋ก, ์ ์ฒด ์๊ฐ๋ณต์ก๋๋ $O(n^2 \log^3 n)$์๋๋ค. ๊ฐ๋จํ ์์ด๋์ด๋ก ์ถฉ๊ฒฉ์ ์ธ ํฅ์์ ์ด๋ฃจ์์์ ๋ณผ ์ ์์ต๋๋ค.

ํนํ $n^2$ ๋น์ทํ ์๊ฐ์ด ๋์๋ค๋๊ฒ ์ค์ํ๋ฐ, ๊ฐ์ ์ด $n^2$ ๊ฐ์ผ ๋ ์ ์ด๋ ์ด ๊ฐ์ ๋ค์ ๊ฒํ ๋ ํด๋ด์ผ ํ๋ฏ๋ก ์ด ๋ฌธ์ ๋ ์ด๋ก ์ $O(n^2)$ ๋ณด๋ค ๋น ๋ฅผ ๋ฐฉ๋ฒ์ด ์์ ์์ต๋๋ค. ์ด๋ ต์ง ์์ ์์ด๋์ด๋ฅผ ์ ์ด์ฉํด์ ์ด์ ๋๊น์ง ๋ณต์ก๋๋ฅผ ๋ด๋ ธ๋ค๋ ์ ์์, Randomized algorithm์ ํ์ ์ ๋ณด์ฌ์ฃผ๋ ์์๊ฐ ์๋๊ฐ ์ถ์ต๋๋ค.

## Extension

์ด ์๊ณ ๋ฆฌ์ฆ์ ์ฌ๋ฐ๋ extension์ $k$-cut์๋๋ค. $k$-cut์ด๋, ๋ธ๋๋ฅผ $k$๊ฐ์ connected component๋ก ์ชผ๊ฐ๊ธฐ ์ํ min cut์ ๊ตฌํ๋ ๋ฌธ์ ์๋๋ค. ์ฐ๋ฆฌ๊ฐ ์ง๊ธ๊น์ง ๊ณต๋ถํ ๋ฌธ์ ๋ $k = 2$ ์ธ ๊ฒฝ์ฐ๋ผ๊ณ  ์๊ฐํ๋ฉด ๋๊ฒ ์ต๋๋ค.

์ด ๋ฌธ์ ๊ฐ ์ฌ๋ฏธ์๋ ์ด์ ๋, ์กฐ๊ธ๋ง extensionํ์ ๋ฟ์ธ๋ฐ ๋ฏธ์น๋ฏ์ด ์ด๋ ต๊ธฐ ๋๋ฌธ์๋๋ค. ์ด ๋ฌธ์ ๋ $k$๋ ์๋ ฅ์ผ๋ก ์ฃผ์ด์ง๋ ๊ฒฝ์ฐ, NP-completeํจ์ด ์ ์๋ ค์ ธ ์์ต๋๋ค. ๊ฐ๋จํ ์๊ฐํด๋ณด๋ฉด, 2-cut์ ์ ์ด๋ s-t min cut ๋ฌธ์ ๋ก ํ์ํ๋ค์ ๊ทธ๊ฑธ ๋๋์ผ๋ก ํธ๋ ๋ฐฉ๋ฒ์ด ์์๋๋ฐ, ์ด ๋ฌธ์ ๋ ํ๋ก์ฐ ๋ชจ๋ธ๋ง์ด ์์ ์ ๋ฉ๋๋ค.

๋ค์ํ ์ํฉ์์ approximation์ ํ๋ค๋๊ฐ ํ๋ ์์ด๋์ด๋ค์ด ์ฐ๊ตฌ๋๊ณ  ์์ง๋ง, ์ฝ์ง ์์ต๋๋ค. Gomory-Hu tree๋ฅผ ์ด๋ค๋๊ฐ ๋ฑ๋ฑโฆ

Karger-Stein algorithm์ $k$-cut์ ๋ํด ๊ต์ฅํ ์ ๋์ํฉ๋๋ค. ๋จ์ํ, ์ต์ข์ ์ผ๋ก ๋จ๊ธฐ๋ vertex๋ฅผ 2๊ฐ๊ฐ ์๋ $k$๊ฐ๋ก ๋จ๊ธฐ๋ฉด ๋ฉ๋๋ค. ์ด ๋ฐฉ๋ฒ์ด ์ฑ๊ณตํ  ํ๋ฅ ์ด ๊ทธ๋์ ์ผ๋ง์ธ์ง, ๋ณต์ก๋๊ฐ ์ผ๋ง์ธ์ง ๋ฑ์ ๊ต์ฅํ ์ด๋ ค์ด ๋ฌธ์ ์๋๋ค.

Interestingly, Karger-Stein ์๊ณ ๋ฆฌ์ฆ์ ์ ๋ง ์ ๋ถ์ํ๋ฉด $k$-cut์ ๋ํด ์ด ์๊ณ ๋ฆฌ์ฆ์ด optimalํ๋ค๋ ๊ฒ์ ๋ณด์ผ ์ ์๋ค๊ณ  ํฉ๋๋ค. ์ด ๊ธ์ ์ ๊ฐ ์ฐ๊ฒ ๋ ์ด์ ๋ ์๊ทธ์  ์ด ์ฃผ์  (Karger-Stein is optimal on $k$-cut) ๋ฅผ ๋ค๋ฃจ๋ ์ธ๋ฏธ๋๊ฐ ์์๊ธฐ ๋๋ฌธ์ ๊ณต๋ถํ๋ ๋ด์ฉ์ ๋ฆฌ๋ทฐํ  ๊ฒธ ํด์ ์ฐ๊ฒ ๋ ๊ฒ์ธ๋ฐ์. ์ธ์  ๊ฐ ์  ๋ผ๋ฌธ์ ์ ๋ถ ์ฝ์ ์ ์์์ง๋ ์ฌ์ค ์์ ์ด ์์ต๋๋ค. ๊ต์ฅํ ์ฌ๋ฐ์ด ๋ณด์ด์ง๋ง ์ฆ๋ช์ด Martingale์ ์ฐ๋ ๋ฑ ์๋นํ ๋ฐฐ๊ฒฝ ์ง์์ ์๊ตฌํ๋ ๊ฒ ๊ฐ์ ๋ณด์์ต๋๋ค. ๊ด์ฌ์ด ์์ผ์  ๋ถ๋ค์ 2019๋ ๋ผ๋ฌธ ๋งํฌ ๊ฐ ์์ต๋๋ค.

๋ณ๋ก ์ผ๋ก, ์ธ๋ฏธ๋์์๋ Karger ์๊ณ ๋ฆฌ์ฆ์ ๋๋คํ๊ฒ edge๋ค์ ์์๋๋ก ๊ณ ๋ฅด๋ ๋์ , ๊ฐ edge๋ค์ exponential clock์ด๋ผ๊ณ  ํด์, essentially ๊ฐ edge์๊ฒ ํน์  ์๊ฐ์ ์ด๋ฒคํธ๊ฐ ์ผ์ด๋  ํ๋ฅ ์ ๋ถ์ฌํ๊ณ  ๊ทธ ์ด๋ฒคํธ๊ฐ ํฐ์ง๋ฉด contractionํด ๋ฒ๋ฆฌ๋ ์์ผ๋ก ์๊ณ ๋ฆฌ์ฆ์ ์ด์ง ๋ค๋ฅด๊ฒ ๋ถ์ํ์ต๋๋ค. ์ด method๊ฐ ์๋ค๋ ๊ฒ์ ๋ค๋ฅธ ๊ณณ์์ ๋ค์์๋๋ฐ, ์ฒ์ ๋ค์์ ๋๋ ์ ๊ทธ๋ ๊ตฌ๋ ๋ผ๊ณ ๋ง ์๊ฐํ๋๋ฐ ์ด๋ฐ์์ผ๋ก ๊ทธ๋ํ ์๊ณ ๋ฆฌ์ฆ์ ์ ์ฉํ๋ฉด ๋ฌธ์ ๋ฅผ ์ฐ์์ ์ธ ๊ณต๊ฐ์ผ๋ก ๋๊ณ ์์ ํด์์ ์ธ ๊ธฐ๋ฒ๋ค์ ์ด์ฉํ ๋ถ์์ด ๊ฐ๋ฅํ๋ค๋ ๊ฒ์ ์๋ก ๋ฐฐ์ ์ต๋๋ค.

1. Stephen Boyd, Lieven Vandenberghe, Convex Optimization, Chapter 4ย โฉ

2. Sparse graph์ ๋ํด์๋ Orlin ๋ฑ ๋ ๋น ๋ฅธ ์๊ณ ๋ฆฌ์ฆ๋ค์ด ์์ง๋ง, ์ฐ์ ์โฆย โฉ

3. Edge contraction์ ์ ์ํ ๋ edge๊ฐ ๊ฒน์น๋ฉด ํ๋๋ง ๋จ๊ธฐ๋ ์ ์๋ค์ด ์๋๋ฐ, ์ ํฌ๋ ๊ทธ๋ฌ์ง ์๊ฒ ์ต๋๋ค.ย โฉ

4. $\left( 1 - \frac{1}{x}\right)^x \leq e^{-x}$ ๊ฐ $1/e$ ๋ณด๋ค ์์์ ์ด์ฉํฉ๋๋ค.ย โฉ

5. ์ Karger ์๊ณ ๋ฆฌ์ฆ์ ์๊ฐ ๋ณต์ก๋ ๋ถ์์์ ๋งํ ๋ฐ์ ๊ฐ์ด Kruskal์ฒ๋ผ ๊ตฌํํ๋ฉด ์ฌ๊ธฐ์ ๋ก๊ทธ๊ฐ ํ๋ ๋ ๋ถ์ต๋๋ค๋ง, ์ฐ๋ฆฌ๋ ์ผ๋จ ๊ตฌํ์ ์ํด์ $O(n)$ ์ ํ contraction์ ์ฒ๋ฆฌํ  ์ ์๋ค๊ณ  ํ๊ฒ ์ต๋๋ค!ย โฉ