6. Maximum Flow & Minimum Cut

1. Mincut & Maxflow problem

 

mincut problem이란 source vertex s, target vertex t를 포함하는 그래프를 s를 포함하는 vertex set A와 t를 포함하는 vertex set B로 분할하였을 때, A->B로 향하는 모든 Edge의 capacity의 합을 최소로 하는 분할을 결정하는 문제이다.

 

maxflow problem이란, 임의의 Edge/Vertex에 대해 아래 조건을 만족하면서 target vertex t로 들어오는 flow를 최대로 만드는 값을 찾는 것이다. 참고로 그래프에서 flow vlaue =  inflow at t 이다.

- Capacity constraint : 0 <= edge's flow <= edge's capacity

- Local equilibrium : inflow = outflow at every vertex (except s and t)

 

2차세계대전때, 특정지점의 공급을 극대화 시키거나, 최소한의 희생으로 공급을 단절시키는 등의 문제를 해결하는데 사용되었다.

 

2. Ford-Fulkerson algorithm

 

Ford-Fulkerson algorithm은 maxflow를 구하는 알고리즘이며, 다음과 같다.

1) 모든 flow를 0으로 설정한다.

2) Augmenting Path를 찾고, flow를 증가/감소시킨다.

3) Augmenting Path를 찾을 수 없을 때까지 2를 반복하며, 최종적으로 t의 inflow가 maxflow가 된다.

 

Augmneting path란 s -> t 인 경로이며, 역방향인 backward edge도 선택될 수 있다. 경로상에서 forward edge는 capacity가 full이 아니면 flow를 증가시키고, backward edge의 경우 capacity가 empty가 아니면, flow를 감소시킨다. 증가/감소하는 flow의 양은 local equilibrium원칙에 따라 경로에서 모두 동일해야 한다.

 

3. Maxflow-Mincut theorem

 

Net flow across a cut (A, B) 이란, 집합 A, B로 나누어지는 하나의 cut에서,  (A -> B인 Edge의 flow 합) - (B -> A인 Edge의 flow합) 이다. 즉, A -> B에서 (총 유입 - 총 유출)이 된다.

 

다음은 maxflow-mincut간의 특별한 관계를 보여준다.

 

Flow-value 보조정리는 다음과 같다.

f를 flow value, (A, B)를 임의의 cut이라고 했을 때, f = net flow across (A, B) 이다. 

 

임의의 cut에 대해, 다음은 자명하다.

net flow across cut (A, B) <= capacity of cut (A, B)   //Capacity가 유입총량보다 더 커야하므로 항상 성립

 

Flow-value lemma에 의해, 다음이 성립한다.

f <= capacity of cut(A, B)    //flow value는 임의의 cut의 capacity보다 작거나 같다

 

이제, 다음의 3가지 명제에 대해 생각해보자.

1) f = capacity of cut (A, B) 인 cut이 존재한다.

2) f는 maxflow이다.

3) Augmenting path가 존재하지 않는다.

 

1 -> 2임을 증명해보자.

f = capacity of cut (A, B) 인 cut이 존재하면, f는 maxflow이다.

만약, 1이 참이고 특정 cut (A, B) 가 있을 때, 임의의 flow f'에 대해 다음이 성립한다.

f' <= capacity of (A, B) = f가 성립하게 되고, f가 maxflow가 아니라면 모순이 되므로 해당 cut에 대해서는 f는 maxflow이다. 따라서 1 -> 2는 참이다.

 

2 -> 3임을 증명해보기위해, contrapositive인, ~3 -> ~2를 증명해보자.

Augmenting path가 존재하면, f는 maxflow가 아니다. Augmenting path가 존재하면 flow의 증가가 가능하므로,  2 -> 3은 참이다.

 

3 -> 1임을 증명해보자.

Augmenting path가 존재하지 않으면, f = capacity of cut (A, B) 인 cut이 존재한다.

A -> B인 cut (A, B)에서, Augmenting path가 존재하지않는다면, 에서 A -> B로 가는 부분(cut)에서 full forward edge 이고 empty backward edge인 특정 cut이 반드시 존재해야한다.

해당 cut에서 유입은 최대이고 유출은 0이므로,  cut capacity = net flow across cut 이 된다. 그런데, flow-value lemma에 의해  f = net flow across (A, B) 이므로, cut capacity = net flow across cut = f 이고, 3 -> 1은 참이 된다.

 

따라서, 순환증명구조로 인해 두개의 정리가 나온다.

2 -> 3 , 3 -> 2가 증명되었으므로,

Augmenting path theorem : A flow f is maxflow iff no augmenting paths

2 ->1 임이 증명되었고,  f = capacity of cut (A, B) 인 cut이 mincut이여야만 f <= capacity of cut(A, B)를 만족하게 되므로

Value of the maxflow = capacity of mincut

 

따라서, maxflow를 구하면 mincut를 도출할 수 있는데, Ford-Fulkerson algorithm으로 maxflow를 구한다음,

source vertex s부터 시작해 탐색하면서 full forward & empty backward 를 만족하는 cut을 찾게되면, cut capacity = net flow across cut = maxflow 가 되어, 이것이 mincut이 된다.

 

4. Running time analysis

 

성능보장을 위해 capacity의 값을 1부터 U사이의 integer값으로 지정하고, flow를 interger값으로 설정하자.

그렇다면 다음이 항상 성립한다.

Augmentaion횟수 <= maxflow값

이것은 augmentation시 최소한 flow가 1은 증가해야하기때문이다. 따라서, maxflow이하횟수의 성능을 보장할 수 있다.

하지만, 실제로 maxflow횟수만큼 augmentation이 이루어진다면 좋지 않은 성능을 보여줄 것이다.

따라서, 알고리즘의 성능은 aumenting path를 탐색하는 방식에 달려있다.

다양한 알고리즘에 대해 성능표는 다음과 같다.

augmenting path	number of paths	implementation
shortest path	<= 1/2EV	queue (BFS)
fatttest path	<= Eln(EU)	prioirty queue
random path	<= EU	randomized queue
DFS path	<= EU	stack (DFS)

 

5. Java Implementation

 

edge에서 capacity와 flow의 관계는 redisual capacity로 표현할 수 있다.

예를 들어, v -> w 방향의 capacity = 10, flow = 9인 Edge가 있다고 해보자.

이것은 v -> w 방향의 residual capacity = 1, w -> w 방향의 residual capacity = 9 인 Edge로 볼 수 있다.

따라서, Augmentation연산시 방향과 증가/감소하는 flow값을 전달함으로서, 연산이 이루어지도록 할 수 있다.

 

FlowEdge의 API는 다음과 같다.

FlowEdge(int v, int w, double capacity)

int from()

int to()

int other(int v)

double capacity()

double flow()

double residualCapacityTo(int v)

void addResidualFlowTo(int v, doule delta)

 

FlowNetwork의 API는 다음과 같다.

FlowNetwork(int V)

void addEdge(FlowEdge e)

Iterable<FlowEdge> adj(int v)

 

6. Application

 

Bipartite matching, Baseball elimination 등 여러 응용에 사용된다.

2012년에 Orlin에 의해 성능은 E^2/logE 정도까지 개선되었지만, Linear time 알고리즘을 찾는 것은 여전히 open problem이다. 실제 사용에서 Push-relabel mehod with gap relabeling을 이용하면, E^(1.5) 시간안에 구할 수 있다.