linear time 2+E approximation algorithm for min cut

David W. Matula의 1993년 논문 을 다룬다. 이 논문에서 다루는 그래프는 가중치가 없는 그래프이다.(multi-edge는 허용한다.)
이 알고리즘의 주목할 만한 점은 선형이면서도 min cut에 대한 강력한 approximation을 제공한다는 점이다. 이 알고리즘은 보통 min cut의 크기를 대략적으로 알아야 할 때(대표적인 예시로 Nagamochi-Ibaraki 1992에서 sparse k-connectivity certificate를 만들기 위해 대략적인 min cut 값을 필요로 함)에 사용된다.

이 논문에선 Maximum Adjacency Search라는 것을 도입한다. 시작 정점 $v$에서 시작하여, 현재까지 탐색한 정점을 $v_1, v_2, ..., v_k$이라 할 때 남은 정점 중 $v_1, v_2, ..., v_k$와 연결된 간선의 개수가 가장 많은 정점을 우선으로 탐색한다. 또한 이 과정에서 현재 탐색한 정점이 $c$일 때, $c$와 인접한 간선 중 아직 방문하지 않은 정점들과 연결된 간선들을 label을 붙여준다. label을 붙이는 값은, 연결된 정점을 $x$라 할 때, $x$에 연결된 간선 중 label 값이 붙은 간선의 개수 + 1 만큼 붙여준다. 임의의 정점 $v$에 대해, $v$와 인접한 간선 중 $v$보다 더 먼저 탐색된 정점과 연결된 간선의 label은 모두 다름을 관찰할 수 있다.

Maximum Adjacency Search는 Double Linked List 등을 이용해 $O(m+n)$에 구현 가능하다.

이 순회를 바탕으로 Level function $l(x)$를 정의한다. $i \lt x \lt i+1$인 $x$에 대해 $l(x)$는 $(v_1, ..., v_i)$와 $(v_{i+1}, ..., v_n)$ 사이 간선의 label 값 중 최댓값이며, $l(i) = max(l(i-0.5), l(i+0.5))$이다.

$F_k$를 label이 $k$인 간선들로 이루어진 subgraph라고 하자. 다음과 같은 핵심적인 Lemma가 성립한다. (편의상 Maximum Adjacency Search 순서를 $v_1, v_2, ..., v_n$이라 하자.

Lemma. 정점 집합 $V'$이 $F_k$에서 하나의 컴포넌트인 것과 다음은 동치이다. : $V' = (v_i, v_{i+1}, ..., v_j)$이고, $[i, j]$는 $l(x) \ge k$를 만족하는 maximal한 범위이다.

이제 본 알고리즘을 설명하겠다. 그래프의 min cut 값을 $\gamma$ 라 하자.

1. 초기 값 설정. $v$를 최소 차수 정점이라 하자. $A \gets v$, $k \gets cut(A, V - A)$, $j \gets [ (1/2 - e) cut(A, V-A) ]$, $H \gets G$.
2. $H$에서 Maximum Adjacency Search를 진행한 후 Lemma를 통해 $F_j$의 컴포넌트를 구한다.
3. $F_j$에서 연결된 컴포넌트들을 하나로 병합한다. 이를 통해 새로운 정점 집합 $V'$과 간선 집합 $E'$를 얻는다. 또한 정점 $a \in V'$에 대해 $A(a)$를 $a$와 같이 합쳐진 원래 그래프에서의 정점 집합으로 정의하자. $H \gets (V', E')$.
4. 만약 $|V'| \ge 2$이고 $ \delta (H) \le k $이면, $H$에서 가장 차수가 작은 정점 $v$에 대해 $A \gets A(v)$, $k \gets cut(A, V-A)$, $j \gets [(1/2 - e) cut(A, V-A)]$이라 하자.
5. 만약 $|V'| = 1$이거나 $j = 0$이면 종료하고, 아니면 2로 돌아가 반복한다.

step 1. 위 알고리즘으로 얻은 $A, j, k$에 대해 다음이 성립한다.
$j \le \gamma \le k$
증명) 먼저 순회에서 가장 마지막에 방문되는 점에 대해선 무조건 합쳐지므로, 이 알고리즘은 언젠가는 종료된다. min cut의 정의상 우변은 자명하고, 만약 $\gamma \lt j$였다면 $j$는 절대 0이 될 수 없으므로 전체가 하나로 합쳐져 $|V'| = 1$이 되어 종료될 것이다. 전체가 하나로 합쳐지기 위해서는 label $j$로 연결된 간선들로 연결되어야 하는데, 잘 관찰해보면 이들은 트리를 이룸을 알 수 있다. 이는 label 1부터 $j-1$까지 모두 성립한다. 병합된 각각에 대해서도 성립한다. 따라서 Edge-disjoint한 $j$개의 tree를 찾을 수 있으므로 $j \lt \gamma$이다. 따라서 모순.

step 2. 위 알고리즘은 $O(n + m)$ 시간 내에 동작한다.
증명) 병합 이후 정점 개수를 $n$, 간선 개수를 $m$, 최소 차수를 $k'$이라 하자. 자명히 다음이 성립한다.
$m \ge nk' / 2$
또한 병합 과정을 생각해보면, 병합 이후 간선들은 모두 label이 j보다 작아야 한다.(클 경우 label j인 간선도 연결되어 있을 것이므로 컴포넌트 정의에 모순) 따라서 병합 이후 과정에서 한 정점은 최대 $j$개의 정점과 연결되어 있으므로, 병합 이후 간선의 개수를 $m'$이라 하면 $m' \lt j'n$이 성립한다. 따라서,
$m' \lt (1/2 - e) k'n \le (1 - 2e) m$
이므로, 한번 시행시 간선의 개수는 $(1-2e)$배가 된다.
$m + (1-2e)m + (1-2e)^2 m + ... = m / (2e)$이므로, 총 수행 시간은 $O(m+n)$이다.

step 1, 2에서 이 알고리즘이 선형 시간에 그래프의 connectivity에 대한 2+e approximation을 제공함을 증명하였다.