k번째 최소 컷 찾기
간선에 가중치가 있는 방향 그래프 $G=(V, E)$를 생각해 봅시다. 시작점 $s \in V$와 끝점 $t \in V$가 주어질 때, $s$와 $t$가 서로 다른 컴포넌트에 있게 되도록 몇 개의 간선을 지울 때, 지우는 간선의 가중치의 합을 최소화하는 문제를 우리는 최소 컷(minimum cut) 문제라고 부릅니다. 이 문제는 최대 유량 최소 컷 정리에 의해 최대 유량 문제로 변형되고, Dinic 알고리즘을 사용한다면 $O(V^2 E)$의 시간 복잡도에 해결할 수 있습니다. 또한, 최대 유량 알고리즘을 수행한 후 시작점 $s$에서 유량이 남아 있는 간선들만을 이용해서 이동할 수 있는 정점과 그렇지 않은 정점으로 나누면 실제 최소 컷을 이룸도 알고 있습니다. 이번 포스팅에서는 이를 확장한 문제인, 그래프에서의 $k$번째 최소 컷을 찾는 문제를 $O(V^3 E k)$의 시간 복잡도에 풀 것입니다.
정의
방향 그래프 $G = (V, E)$의 각 간선 $e \in E$에 가중치 $w(e)$가 주어집니다. 두 정점 $s, t \in V$가 주어졌을 때, 다음 조건을 만족하는 집합 $X \in V$들을 생각합니다.
$s \in X, t \in V \setminus X$
위 조건을 만족하는 각 $X$에 대해, 다음과 같은 집합 $D \in E$가 정의됩니다. 집합 $D = \begin\{e = (u, v); u \in X, v \not\in X \end\}$에 속한 간선의 가중치의 합 $c(D) = \sum_{e \in D} w(e)$을 최소화하는 문제를 최소 컷 문제라고 합니다.
이를 확장해 $k$번째 최소 컷 문제를 정의합니다. $k$번째 최소 컷 문제란, 위 조건을 만족하는 집합 $D$들 가운데, 가장 $c(D)$가 작은 $k$개의 집합 $D_1, D_2, \cdots, D_k$를 구하는 문제입니다.
두 번째 최소 컷 찾기
위 문제를 풀기 위해, 먼저 $k=2$일 때의 두 번째 최소 컷 찾기 문제를 $O(V^3 E)$에 풀 것입니다. 우리가 첫 번째 최소 컷을 알고 있다면, 두 번째 최소 컷은 어떻게 구할 수 있을까요? 제일 먼저 생각할 수 있는 방법은, 첫 번째 최소 컷 $D_1$에 속한 각 간선에 대해서, 해당 간선을 포함하지 않은 최소 컷을 찾는 것입니다. 이들 중 가장 가중치의 합이 작은 컷이 두 번째 최소 컷인 $D_2$가 될 것입니다.
위 알고리즘은 최대 유량 최소 컷 정리에 의해, $D_1$에 포함되는 각 간선에 대해, 해당 간선의 가중치를 무한으로 두고 최대 유량을 구하는 것과 같습니다. 따라서, Dinic 알고리즘을 $O(E)$번 실행해서 두 번째 최소 컷을 찾을 수 있습니다. 이 과정의 시간 복잡도는 $O(V^2 E^2)$가 됩니다.
이 때, 각 간선을 포함하지 않은 최소 컷을 조금 더 빠르게 구하는 방법을 생각해 봅시다. 다시 유량의 관점으로 생각해 보면, 간선 $(u, v)$의 가중치를 무한으로 바꾸었을 때 추가될 수 있는 증가 경로(augumenting path)는 모두 간선 $(u, v)$를 지납니다. 즉, 간선 $(u, v)$를 기준으로 증가 경로를 양쪽으로 나누어 생각할 수 있습니다. 따라서 간선의 가중치를 늘인 뒤 $s$에서 $t$로 추가로 흘릴 수 있는 유량은, $s$에서 $u$로 추가로 흘릴 수 있는 유량과 $v$에서 $t$로 추가로 흘릴 수 있는 유량 중 작은 값이 됩니다. 두 값을 계산할 때에 간선 $(u, v)$의 가중치가 무한대로 변했다는 사실을 사용하지 않으므로, 이들을 독립적으로 전처리 할 수 있습니다. 각 정점 $x$에 대해서, $s$에서 $t$로 향하는 최대 유량만큼 흐르고 있는 상태에서 $s$에서 $x$로 추가로 흘릴 수 있는 유량을 $\alpha (x)$, 같은 상태에서 $x$에서 $t$로 추가로 흘릴 수 있는 유량을 $\beta (x)$로 둡시다. 그러면 두 번째 최대 유량, 즉 두 번째 최소 컷은,
$ c(D_1) + \min_{(u, v) \in D_1} \left( \min\left( \alpha(u), \beta(v) \right) \right) $
가 됩니다. $\alpha(x)$와 $\beta(x)$를 전처리 하기 위해서 Dinic 알고리즘을 $O(V)$번 사용하여야 합니다. 이 때, 각 $(u, v) \in D_1$에 대해서 $u \in X_1$이고, $v \not\in X_1$이므로, $X_1$에 속하는 정점들에 대해서는 $\alpha (x)$만을, 속하지 않는 정점들에 대해서는 $\beta(x)$만을 구하면 된다는 사실도 확인할 수 있습니다. 따라서, Dinic 알고리즘을 총 $V-1$번 사용하여 두 번째 최소 컷을 알 수 있게 됩니다. 이 과정의 시간 복잡도는 $O(V^3 E)$가 됩니다.
$k$번째 최소 컷 찾기
이미 짐작했겠지만, $k$번째 최소 컷을 찾는 알고리즘은 위에서 소개한 두 번째 최소 컷을 찾는 알고리즘을 반복해서 적용시켜서 얻습니다. 전체적인 아이디어는 다음과 같습니다.
먼저, 첫 번째 최소 컷과 두 번째 최소 컷을 구합니다. 그리고, 가능한 컷 $D$들의 집합 $\mathcal{D}$를 적절히 두 집합 $\mathcal{D}_1$, $\mathcal{D}_2$로 나눕니다. 이 때 $\mathcal{D}_1$에는 첫 번째 최소 컷 $D_1$이 들어가게, $\mathcal{D}_2$에는 두 번째 최소 컷 $D_2$가 들어가게 합니다. 그리고 $\mathcal{D}_1$과 $\mathcal{D}_2$ 각각에 속하는 컷들 중에서 두 번째로 최소인 컷을 구합니다. 구한 두 개의 컷 중 작은 것이 세 번째 최소 컷이 되겠죠. 이제 $\mathcal{D}_1$과 $\mathcal{D}_2$ 중 세 번째 최소 컷이 나온 집합을 다시 절반으로 나누고, 다시 이 두 집합들 안에서 두 번째로 최소인 컷들을 구하고, 구한 세 가지의 ‘두 번째 컷’들 중 가장 작은 것이 다시 네 번째 최소 컷이 됩니다. 이 과정을 $k$번 반복합니다. 그러면 각 과정에서 하나의 집합을 둘로 나누고, 각 나눠진 집합에 대해서 두 번째 최소 컷을 찾는 과정을 수행하게 되므로, 각 과정에서는 두 번째 최소 컷을 찾는 알고리즘을 두 번 반복하게 됩니다.
그러나, 한 가지 문제가 있습니다. 우리가 두 번째 최소 컷을 찾은 알고리즘은 가능한 컷들의 전체 집합 $\mathcal{D}$ 안에서 두 번째 최소 컷을 찾을 수 있었지, 이 집합의 부분집합 안에서 두 번째 최소 컷을 찾는 방법은 고려하지 않았죠. 그럼에도 이 때에 가능한 컷들의 집합을 ‘잘’ 나누면 두 번째 최소 컷을 찾을 때 썼던 알고리즘을 재사용할 수 있습니다. 아래에는 그 방법에 대해 서술합니다.
먼저, 첫 번째 최소 컷 $D_1$과 두 번째 최소 컷 $D_2$를 구한 다음, $D_1$에는 들어 있지만 $D_2$에는 들어있지 않은 간선을 하나 골라 $e_2$라 합시다. 이런 간선은 무조건 존재합니다. 이 때, $\mathcal{D}_1$과 $\mathcal{D}_2$를,
$\mathcal{D}_1 = \left{ D \in \mathcal{D}; e_2 \in D \right}$
$\mathcal{D}_2 = \left{D \in \mathcal{D}; e_2 \not\in D \right}$
로 둡니다. 즉, $\mathcal{D}_1$은 $e_2$를 포함하는 컷들, $\mathcal{D}_2$는 $e_2$를 포함하지 않는 컷들을 담고 있습니다. 이를 체계화하기 위해 아래와 같이 두 집합 $IN \in E$과 $OUT \in E$을 정의합니다. 변수들에 붙은 윗첨자 $2$는 두 번째 컷을 구하는 과정의 변수라는 뜻입니다.
$\mathcal{D}_1^2 = \left{ D \in \mathcal{D}; IN_1^2 \subseteq D, OUT_1^2 \not\subseteq D \right}, IN_1^2 = \left{ e_2 \right}, OUT_1^2 = \emptyset$
$\mathcal{D}_2^2 = \left{ D \in \mathcal{D}; IN_2^2 \subseteq D, OUT_2^2 \not\subseteq D \right}, IN_2^2 = \emptyset, OUT_2^2 = \left{ e_2 \right}$
이와 같은 형태의 집합에 속하는 두 번째 최소 컷을 찾는 방법은 간단하며, 아래에 서술합니다. 이제 위 두 집합 안에서 각각 두 번째 최소 컷을 찾으면, 둘 중 작은 컷이 세 번째 최소 컷이 됩니다. 세 번째 최소 컷 $D_3$이 $\mathcal{D}_2^2$의 원소라고 합시다. 이 때, $e_3 \in D_2 \setminus D_3$을 잡으면 위와 같은 방법으로 $\mathcal{D}_2^2$를 $D_2$가 속한 $\mathcal{D}_2^3$와 $D_3$이 속한 $\mathcal{D}_3^3$으로 나눌 수 있게 됩니다.
$\mathcal{D}_1^3 = \mathcal{D}_1^2$
$\mathcal{D}_2^3 = \left{ D \in \mathcal{D}; IN_2^3 \subseteq D, OUT_2^3 \not\subseteq D \right}, IN_2^3 = \left{ e_3 \right}, OUT_2^3 = \left{ e_2 \right}$
$\mathcal{D}_3^3 = \left{ D \in \mathcal{D}; IN_3^3 \subseteq D, OUT_3^3 \not\subseteq D \right}, IN_3^3 = \emptyset, OUT_3^3 = \left{ e_2, e_3 \right}$
일반적으로, $\mathcal{D}1^{k-1}$부터 $\mathcal{D}{k-1}^{k-1}$까지 모두 구성을 끝냈을 때, $\mathcal{D}_x^{k-1}$이 이들 중 두 번째 최소 컷이 가장 작은 것이라고 합시다. 이 때 $\mathcal{D}_i^k$를 다음과 같이 구성할 수 있습니다.
$\mathcal{D}_i^k = \left{ D \in \mathcal{D}; IN_i^k \subseteq D, OUT_i^k \not\subseteq D \right}$
$IN_x^k = IN_x^{k-1} \cup \left{ e_k \right}, OUT_x^k = OUT_x^{k-1}$
$IN_k^k = IN_x^k, OUT_k^k = OUT_x^k \cup \left{ e_k \right}$
$IN_i^k = IN_i^{k-1}, OUT_i^k = OUT_i^{k-1} (i = 1 \cdots k-1, i \neq x)$
$(e_k \in D_x \setminus D_k)$
마지막으로, 이와 같은 형태의 집합 $\mathcal{D}_i^k = \left\{ D \in \mathcal{D}; IN_i^k \subseteq D, OUT_i^k \not\subseteq D \right\}$ 안에 있는 두 번째 최소 컷을 구하는 방법을 알면 됩니다. 간단히, 아래와 같이 원래 그래프를 변형한 다음 위 단락에 소개한 두 번째 최소 유량 알고리즘을 적용하면 됩니다.
- $IN_i^k$에 속하는 각 간선 $(u, v)$에 대해, $u$를 유량 알고리즘의 시작점에 추가하고, $v$를 유량 알고리즘의 끝점에 추가합니다. 최대 유량 알고리즘이 종료된 뒤에는 유량이 남은 간선들만을 이용해 $u$에서 $v$로 가는 경로가 없어지므로, 특히 $(u, v)$는 최소 컷에 포함되게 됩니다.
- $OUT_i^k$에 속하는 각 간선에 대해, 이 간선의 가중치를 무한대로 만듭니다.
이와 같이 두 번째 최소 컷 알고리즘을 $k-1$번 적용하면 $k$번째 최소 컷을 구할 수 있습니다. 전체 시간 복잡도는 $O(V^3 E k)$입니다.
그리고…
설명한 알고리즘을 사용한 문제는 2016년도 ICPC 아시아 평양 리저널에 출제되었습니다. 그러나 안타깝게도 이 문제를 해결한 팀의 수 등 통계는 확인할 수 없습니다.
그리고 사실, 이 방법을 원래 제안했던 글에서는 $O(V^2 E)$에 작동하는 Dinic 알고리즘 대신 $O(V^3)$에 작동하는 Karzanov의 알고리즘을 사용할 것을 제안했습니다. Karzanov의 알고리즘을 사용하면, 전체 $O(V^4 k)$의 시간 복잡도에 $k$번째 최소 컷을 찾을 수 있습니다. 하지만 알고리즘 문제 해결의 영역에서 Karzanov의 알고리즘은 과하게 복잡할 뿐더러, Dinic의 알고리즘을 사용하더라도 해당 문제를 맞을 수 있을 것으로 보입니다.
참고문헌
- H. Hamacher, “An O(n^4) algorithm for finding the k best cuts in a network”, Operations Research Letters 1, 186-189 (1982)