민컷 이야기

(2017.10.06 초판)

(2017.10.07 Weeping Fig 문제의 해설을 보완해서 다시 작성했다.)

전대프연 2016. 분단의 슬픔

최소 비용을 구하고자 한다 -> min cut과 최소 비용이 동치임을 찾는다 -> min cut으로 풀린다 류의 문제 중에서 제일 쉬운 것 같다. 이유는 간단하다. 그런 문제는 보통 풀 수 없거든

source와 sink를 만들고, 그 사이에 사람들을 정점과 간선으로 적절히 이어서, source쪽 cut에 속한 정점을 A 진영 / 그렇지 않은 정점을 B 진영으로 둘 것이다. 

방법은 간단하다. Min cut에 속하는 정점 집합을 $S$라 하고, 그렇지 않은 정점 집합을 $T = V\setminus S$ 라 하면,

 * 무조건 $S$에 들어가는 정점은 source와 $\infty$ cost 간선을 이어주고, 무조건 $T$에 들어가는 정점은 sink와 $\infty$ 간선을 이어준다. 이렇게 할 경우 민컷을 구했을 때 항상 원하는 집합에 들어가게 되어 있다.

 * 두 정점이 다른 진영에 들어가서 발생하는 cost는 두 정점을 잇는 간선이 cut되어서 발생하는 cost와 같으니, 두 정점 간에 $W[i, j]$ 용량의 에지를 만들어 준다.

이후 Dinic's algorithm으로 민 컷을 구해주면 된다.

KUPC 2017. Make a Potion

오늘 돌았다 참교육당한 문제. 일단 설명의 편의를 위해서 $v_i, x_i, y_i = 1$로 두고 시작하겠다. 이렇게 되면 $h_i$의 값을 얻거나, 못 얻게 되며, $s_i$에서 값을 얻었다면, $e_i$에서도 값을 얻어야 한다는 식으로 제약 조건이 생긴다. 이렇게 했을 때 그래프 빌딩은 대략 이렇게 한다. $X$는 충분히 큰 수라 하자. 

* source에서 정점 $i$로 $X$ 용량의 에지를 잇는다.

* 정점 $i$에서 sink로 $X - h_i$ 용량의 에지를 잇는다.

정점 $i$가 컷 안에 있으면 $h_i$를 얻었고, 아니면 못 얻었다는 느낌의 빌딩이다. 이런 식으로 한 후 min cut를 생각해 보면, $nX - $ (취한 이득) 꼴의 값이 나올 것이며, 취한 이득을 계산할 수 있다. (왜 $nX$일까? $X$는 큰 값이고 자명히 $nX$의 비용으로 다 끊을 수 있기 때문에 답은 최대 $nX + c$ 일 것이다. 한편 $(n-1)X$로는 절대 끊을 수 없다. 고로 $X$는 총 $n$번 등장한다.)

제약 조건을 추가하는 것은, 정점 $i$에서 $j$로 $\infty$ 용량의 에지를 이어주면 된다. 이렇게 된다면, $i$가 컷 안에 있을 때 $j$가 무조건 컷 안에 존재하고, $h_j$를 무조건 얻는 상황이 생기기 때문이다. 이러한 그래프에서 min cut을 구하면 답을 구할 수 있다.

물론, $v_i, x_i, y_i = 1$이 성립을 하지 않는다는 치명적인 단점이 있는데, 이를 해결하기 위해서 정점을 많이 만들자. $V(i, w)$가 컷에 들어갔다면, $i$에서 $w$ 이상의 용액을 사용했다는 뜻이다. 이 때,

* source에서 정점 $V(i, 0)$으로 $X$ 용량의 에지를 잇는다.

* 정점 $V(i, j)$에서 $V(i, j+1)$로 $X - h_i * j$ 용량의 에지를 잇는다.

* 정점 $V(i, v_i)$ 에서 sink로 $X - v_i * h_i$ 용량의 에지를 잇는다.

* 정점 $V(a_i, x_i)$에서 $V(b_i, y_i)$ 로 $\infty$ 용량의 에지를 잇는다.

와 같이 모델링을 일반화해주면 모든 용량을 대변할 수 있게 된다. 정점이 굉장히 많긴 하지만, 실제로 degree 2가 아닌 정점들(예 : $V(i, v_i)$ 혹은 $V(a_i, x_i)$, $V(b_i, y_i)$.. )만 쓸모가 있다. 그 사이에 있는 간선은 최솟값으로 퉁쳐주면 그래프의 크기가 충분히 작아서 min cut을 구할 수 있다.

NEERC 2006. 팀의 난이도

항상 말하지만 분수는 파라메트릭이니까 써 주고 시작하자. 이 문제는 최소화해야 하는 식을 잘 정리해서 민 컷으로 바꿔주는 것이 목표이다. $n$ 개의 값이 있고, $w_{i, j}, a_i, b_i \geq 0$ 일 때, 민 컷을 사용하면

$\sum_{i\in S, j\notin S}{w_{i, j}} + \sum_{i\in S}{b_i} + \sum_{i\notin S}{a_i}$

의 최솟값을 만드는 $S$를 구할 수 있다. 분단의 슬픔 문제에서 사용했던 정의와 완전히 일치함을 주목하자! 

$T$ 이하의 밀도를 가지는 정점의 부분집합이 존재하는 지를 판별하는 문제를 생각해 보자. $|E| / |V| \geq T$ 라는 것은 $|V| * T - |E| \leq 0$ 이라는 것이다. 고로 $|E| - |V| * T$ 를 최소화한 다음에, 이것이 0 미만인지를 판별하면 될 것이다. (0 미만임에 유의하자! 이유는, 공집합을 걸러야 하기 때문이다. 민 컷에서는 $S$가 공집합이 나올 수 있지만, 여기서는 $S$가 공집합이면 안 된다.) 아까와 최대한 비슷하게 식으로 쓰면

$-\sum_{i\in S, j\in S}{adj_{i, j} * 0.5} + \sum_{i\in S}{T}$ ($adj_{i, j}$ 는 인접행렬이다.)

이제 식을 열심히 써서 위 식과 비슷하게 끼워맞춰주면 된다. 열심히 식을 바꿔보자.

$-\sum_{i\in S, j\in S}{adj_{i, j} * 0.5} + \sum_{i\in S}{T}$

= $-\sum_{i\in S, j\in V}{adj_{i, j} * 0.5} + \sum_{i\in S, j\notin S} {adj_{i, j} * 0.5} + \sum_{i\in S}{T}$

= $-\sum_{i\in S}{0.5 * deg_i} + \sum_{i\in S, j\notin S} {adj_{i, j} * 0.5} + \sum_{i\in S}{T}$ ($deg_i = i$의 degree.)

= $-|E| + \sum_{i\notin S}{0.5 * deg_i}+ \sum_{i\in S, j\notin S} {adj_{i, j} * 0.5} + \sum_{i\in S}{T}$

= $-|E| +\sum_{i\in S, j\notin S} {adj_{i, j} * 0.5} + \sum_{i\in S}{T} + \sum_{i\notin S}{0.5 * deg_i}$

분단의 슬픔을 푸는 프로그램에 그대로 이 식을 때려박으면 풀 수 있다.

BOJ 13367. Weeping Fig

일반적으로 Min Cut은 어떠한 정점 s, t가 주어졌을 때 둘 사이를 끊는 방법을 찾는데, 여기서는 s, t가 주어지지 않고 그냥 그래프를 끊는 방법을 뭐든지 찾으면 된다. 식으로 써 보면

$Min_{S \subset V(G)}{\sum_{i\in S, j\notin S}{W_{i, j}}}$ 

과 같다. 

여기서 중요한 것은 $S$가 공집합이나 전체 집합이 되면 안 된다는 것이다! 그렇지 않다면 $W_{i, j} \geq 0$ 일 때 당연히 공집합을 잡고 0을 답이라 할 수 있기 때문이다. 전체 집합이어도 상황은 똑같다. $S$가 공집합 / 전체 집합이 되는 것이 별 것 아닌 것 같지만, 사실상 이 문제의 핵심이다. 직관적으로 최적해가 $|S| = 1$ 같은 조건을 넣어보고 싶지만, 이는 아주 쉽게 반례가 나온다.

우리가 알고 있는 방법으로 이 문제를 해결해 보자. 관련 내용은 모두 "유량 관련 알고리즘 정리" 에 적혀 있다.

 * 먼저, $S$에 속하는 정점 $x$, $S$에 속하지 않는 정점 $y$를 고정시키고 x - y 간의 minimum cut을 maximum flow로 구할 수 있다. Dinic's algorithm을 사용했다고 가정하면 이 알고리즘의 시간 복잡도는 $O(V^4E)$ 이다.

 * Gomory-Hu Tree라는 방법을 통해서, $O(V)$ 번의 maximum flow 연산을 통해서 $x - y$ 간의 minimum cut을 전부 계산할 수 있다. 이 알고리즘의 시간 복잡도는 $O(V^3E)$ 이다.  

.. 모두 복잡하며, 시간 복잡도가 전혀 맞지 않는다.

한편, 일전에 블로그에서 소개했던 Karger's nondeterministic min-cut algorithm을 떠올려 보자. 이 방법은 랜덤화된 방법을 사용하여 s - t cut을 구하며, 특히 Maximum Flow를 전혀 사용하지 않는다는 특징이 있다. 이 문제에서는 에지에 가중치가 있지만, Global min cut 문제는 오히려 Min-cut Max-flow theorem과 관련 없는 간단한 방법이 존재할 수 있다는 힌트를 준다.

실제로, Stoer-Wagner Algorithm은 생각보다 아주 간단한 방법으로 $O(V^3)$ 내지는 $O(VElgE)$에 Global min cut을 해결한다. 피보나치 힙을 사용하면 $O(VE + V^2lgV)$도 가능하다.

그 방법은 다음과 같다. MinimumCutPhase() 라는 $O(V^2)$ / $O(ElgE)$ (피보나치 힙 사용시 $O(E+VlgV)$) 루틴에서, 어떠한 정점 $s, t$간의 minimum cut을 구할 수 있다고 하자. ($s, t$는 정할 수 있는 것이 아니라 그냥 반환되는 것이다.)

우리는 $s, t$ cut을 구했으니, $s, t$가 아닌 cut도 구해야 할 것이다. $s, t$ cut이 아니라는 것은 $s, t$가 같은 집합에 속해있다는 뜻이다. 고로, 그 답이 $s, t$를 하나의 정점으로 합쳐준 (edge contraction) 그래프의 minimum cut과 똑같다. 하나의 정점으로 합쳐준다는 것은, 원래 s와 t를 잇던 에지를 지우고, s나 t를 향하던 에지들의 가중치를 합해주면 된다. 예를 들어, $v, s$를 잇는 가중치 $w(v, s)$ 에지와 $v, t$를 잇는 가중치 $w(v, t)$ 에지가 있다면, 새롭게 $v, st$를 잇는 가중치 $w(v, s) + w(v, t)$ 에지가 생기는 것이다. 

이렇게 생긴 정점 $|V|-1$ 개의 그래프에서 minimum cut을 구하고, 재귀적으로 $|V| = 1$일 때까지 반복하면 $O(V^3)$ 알고리즘을 얻을 수 있다.

이제 MinimumCutPhase()에 대해서 알아보자. MinimumCutPhase()의 작동 원리는 프림 알고리즘과 아주 유사한데, 맨 처음에 아무 정점 $a$를 잡아서 집합 $A$에 넣고, $A$에 속하지 않으면서, 현재 집합 $A$와 가장 "강하게" 연결되어 있는 정점들을 하나씩 추가하는 것이다. 집합 $A$와 가장 가중치 작은 간선으로 연결되어 있는 간선을 추가하는 프림 알고리즘과 유사하다. 어떠한 정점 $v$의 "강함"은, $v$에서 $A$로 연결된 간선들의 가중치 합을 뜻한다. 이 합이 가장 큰 것을 넣어준다는 것이다. 이 때 $A$에 가장 마지막에 추가된 정점의 "강함" 이 min cut의 크기이고, $A$에 두번째로 마지막 / 마지막에 추가된 정점이 MinimumCutPhase()가 찾아낸 정점 $s, t$이다.

이제 이에 대한 증명을 소개한다. 링크 정의가 많으니 차근차근 읽어보길 바란다. 정의가 많아서 그렇지 복잡하진 않다.

 정의 1. 그래프의 어떤 최소 s - t컷을 $X$라 정의하자. 

 정의 2. $A$에 추가되는 정점을 순서대로 나열했을 때 $a, p_1, p_2, \cdots, s, t$ 라고 하자. 어떠한 정점 $v \neq a$가, $v$ 직전에 $A$에 들어간 정점과 반대쪽에 속한다면 (즉 $v \in X, pred(v) \notin X$ 혹은 $v \notin X, pred(v) \in X$) 이 정점을 "active" 하다고 하자. 순열에서 봤을 때, $v$ 직전에 $A$에 들어간 정점은, $v$의 바로 왼쪽에 있을 것이다. 

 정의 3. $v$보다 먼저 $A$에 들어간 정점의 집합을 $A_v$라 하자. 순열에서 봤을 때, $v$ 전에 등장하는 정점의 집합이다.

 정의 4. 컷에서 $A_v \cup \{v\}$를 induced했을 때의 weight 합을 $C_v$라고 하자. 여기서 induced했다는 말을 설명하자면, 컷 $X$의 가중치 합은 $sum_{i\in X, j\notin X}{W_{i, j}}$ 였는데, 이제는 $sum_{i\in X, j\notin X, i, j \in (A_v \cup \{v\})}{W_{i, j}}$ 임을 뜻한다. 즉, 전체 컷에서 저 집합에 양 끝이 속하는 에지들만 사용한 것이다. 

 정의 5. $w(S, t)$ 는 $S$에 속하는 모든 정점들과 $t$와의 에지 가중치 합이라 하자.

이제, 모든 active한 정점 $v$에 대해서 $w(A_v, v) \leq C_v$가 성립한다. 이는 active한 정점에 대해서 수학적 귀납법을 사용해서 증명할 수 있다.

기저 조건을 살펴 보자. 가장 먼저 등장한 active한 정점 $x$에 대해서는, 정의 상 $w(A_x, x) = C_x$임을 알 수 있다. $A_x$가 모두 $x$와 다른 집합에 속하기 때문이다. 이제 귀납 조건을 살펴보자. active한 정점 $v \neq x$와, $v$ 바로 전에 순열에서 등장한 active한 정점 $u$에 대해서 다음이 성립한다. (즉, 순열에서 $v$보다 전에 등장하는 가장 늦게 등장한 active한 정점이 $u$이다.) 

 * $w(A_v, v) = w(A_v - A_u, v) + w(A_u, v)$ (자명하다.)

 * $w(A_u, v) \leq w(A_u, u)$ (자명하다. 이 알고리즘에서는 $w(A_{v}, v)$가 가장 큰 $v$를 선택했기 때문이다. 만약 저것이 거짓이면 $v$가 $u$보다 먼저 추가되어야 한다.) 

 * $w(A_u, u) \leq C_u$ (귀납 가정이다.)

 * $w(A_v, v) = w(A_v - A_u, v) + C_u$ (위 식을 스까면 된다.)

 * $w(A_v - A_u, v) + C_u \leq C_v$ (귀납 가정에 의해, $u, p_i, p_{i+1}, \cdots$ 가 모두 $v$랑 다른 집합에 속하는 것을 관찰하자. 그렇지 않을 경우 가정에 모순이다. 고로 이들 에지는 모두 $C_v$ 안에 존재하지만 $C_u$ 안에는 없다. 고로 부등식이 성립한다.)

 * $w(A_v, v) \leq C_v$ (위 식을 스까면 끝!)

$t$는 active한 정점이다. 왜냐면 $X$가 s - t cut이기 때문에 $s \in \bar{X}, t \in X$가 성립하기 때문이다. 고로 이 명제가 성립한다면 $w(A_t, t) \leq C_t$ 이다. 한편, 실제 컷을 추적하는 것은 $t$에 연결된 간선을 전부 끊음으로 자명하게 찾을 수 있다. 고로 $w(A_t, t) \geq C_t$ 도 성립한다. 마지막으로, $A_t \cup \{t\}$는 정점 셋 그 자체이기 때문에 $C_t$에서 induced됐다는 것은 의미가 없다. 그냥 컷 그 자체이다. 고로 $w(A_t, t)$ 가 s - t cut이다.