Maximum Flow and Minimum Cut

 

* 이 포스트는 알고리즘의 기초에 대한 개인 학습용으로 작성한 포스트입니다.

 

 

Minimum Cut Problem

Source와 Sink가 존재하는 directed graph를 flow network라 한다. 각 edge는 capacity를 가진다. 아래 그림과 같이 cut을 정했을 때 cut의 capacity 합이 최소값을 찾는 문제를 Minimum cut problem이라 한다. 

 

 

 

 

Maximum Flow Problem

Flow는 capacity 내에서 흐를 수 있는데, source부터 sink까지 흐를 수 있는 최대 flow를 찾는 문제를 Maximum flow problem이라 한다. Cut을 기준으로 나가는 edge와 들어오는 edge를 통해 flow를 계산할 수 있다.

 

 

 

 

 

Weak duality

flow 값은 항상 cut의 capacity값 보다 같거나 작다.

 

Pf )

 

 

 

 

 

Ford-Fulkerson Algorithm

Maximum flow algorithm은 greedy algorithm으로 풀 수 없다. (반례 존재)

현재 흐르는 Flow를 뜻하는 residual edge를 만들어 해결한다.

 

 

 

 

Augmenting path theorem

augmenting path가 더 존재하지 않으면 f는 maximum flow이다.

 

Max-flow min-cut theorem

Maximum flow와 Minimum cut는 같다.

 

Pf ) 아래의 3개의 명제는 동치이다.

(i) $v(f) = cap(A, B)$인 cut이 존재한다.

(ii) $f$는 maximum flow이다.

(iii) $f$에 대해서 더이상 augmenting path가 존재하지 않는다.

 

(i) -> (ii)

Weak duality lemma에 의해 flow가 더 커질 수 없으므로 maximum flow이다.

 

(ii) -> (iii)

대우법 사용.

Augmenting path가 존재하면, 알고리즘 상에서 f를 무조건 증가시킬 수 있기 때문에 만족한다.

 

(iii) -> (i)

Augmenting path가 존재하지 않는다고 가정하자.

(A, B) set을 나누었을 때, 더 증가시킬 수 없는 상태이므로 A -> B로 가는 edge는 capacity를 모두 사용한 상태, B -> A로 가는 residual edge는 capacity를 하나도 사용하지 않는 상태여야한다. (아래 그림 참고)

 

 

다음 식에 의해 유도가 가능하다.

 

 

따라서, 3개의 명제는 동치이다.

 

 

Running time

모든 capacity는 정수여야한다. (1부터 C까지)

 

Augmenting path를 찾는 과정은 flow를 적어도 1 증가시키므로 적어도 nC iterations 실행된다.

한번 augmenting path를 찾는 과정은 $O(m)$

 

따라서, running time : $O(nCm)$

 

 

 

Capacity Scaling

위에서 보였듯이 running time이 C에 따라 바뀌기 때문에 완전히 polynomial하지 않다. 예를 들어, C=10000이면 iteration이 최대 10000번 실행되어 비효율적으로 실행된다. 이는 bottleneck이 작은 path를 선택함으로써 생긴 문제이므로, 좋은 augmenting path를 찾는 것이 Ford-Fulkerson algorithm에서 중요하다.

 

그 방법으로, scaling parameter $\Delta$를 정의하는 것이다.scaling parameter를 정하면 $G_f(\Delta)$는 $\Delta$보다 작은 capacity를 가지는 edge를 제거한 residual graph를 뜻한다.

 

 

 

 

초기값 $\Delta$\는 C보다 큰 최소의 2의 거듭제곱으로한다. Capacity scaling을 적용한 알고리즘은 아래와 같다.

 

 

 

 

Correctness

위의 알고리즘에서 residual graph의 capacity는 정수값으로 유지된다. Ford-Fulkerson algorithm이 augmenting path가 존재하기 전까지 아무 path를 설정해도 상관없다.

마지막 $\Delta = 1$일 때, $G_f(\Delta) = G_f$이고 더 이상 augmenting path가 존재하지 않을 때까지 실행되므로 Correctness가 보장된다.

 

 

Running time

1. 바깥쪽 for loop은 $1 + \lceil logC \rceil$만큼 반복된다.

 

2. scaling parameter가 $\Delta$ 일 때, 최종 maximum flow는 적어도 $v(f) + m\Delta$보다 작거나 같다.

 

Pf ) 

 

s가 포함된 set을 A, t가 포함된 set을 B라 할 때, 

A -> B 방향의 edge는 여분의 공간이 $\Delta$를 넘을 수 없다.

따라서, $c_e - f(e) < \Delta$

B -> A 방향의 edge (residual edge)에서 동일한 논리로,

$f(e) < \Delta$

 

따라서, 아래의 식으로 유도 가능하다.

 

 

3. 한번의 scaling phase에서 augumenting path는 최대 2m번 찾으면 된다.

f를 그전의 scaling phase에서 flow라 하자. 그러면 현재의 flow에 대한 식은 아래와 같다.

 

$v(f^*) \le v(f) + m(2 \Delta)$

 

각 iteration에서 flow는 $\Delta$만큼 update되는데 2m번보다 더 update하면 위의 식을 어기게 되므로 최대 2m번 찾으면 된다.

 

따라서 1~3에 의해 augmenting path를 찾는데 $m$만큼 소요되고, 최대 $mlogC$번 찾으므로

running time은 $O(m^2logC)$이다.

 

 

 

Bipartite Matching

하나의 노드가 1개의 edge만 가지도록 subset을 구성하는 것을 matching이라한다. Bipartite graph에서 matching이 최대가 되도록하는 것을 Bipartite matching이라 한다.

 

 

 

 

 

위의 문제를 Maximum flow problem으로 변형하여 해결할 수 있다. 각 L, R의 node간의 연결은 그대로 두고, source는 L과, target은 R과 하나씩 edge를 연결하여 아래 그림과 같이 구성한다. Edge의 capacity는 모두 1로 설정한다. (L, R간의 edge는 무한으로 설정해도 무관)

 

 

 

 

 

위의 graph에서 Maximum flow algorithm을 풀고 flow가 흐르는 edge를 선택하면 maximum matching이 된다. 

 

 

Correctness

Max cardinality matching의 graph를 G, max flow의 graph를 G'라 하자.

 

1. Maximum cardinality matching은 maximum flow보다 작거나 같다.

flow constraint를 만족함을 증명하면 된다.

 

a. capacity constraint : edge당 많아 봤다 flow 1흐르므로 capacity를 넘지 않는다.

b. conservation constraint : 구조상으로 s, t를 제외한 노드의 flow 총합은 0이 된다.

 

2. Maximum cardinality matching은 maximum flow보다 크거나 같다.

Maximum flow graph에서 Integrality theorem에 의해 maximum flow k는 integer이다.

각 L, R의 node는 edge 1개만 가지므로 matching 만족.

L, R을 나누도록 cut을 설정하면 matching 수는 maximum flow와 같다.

 

 

Running time

Generic augmenting path : $O(mval(f^*)) = O(mn)$

Capacity scaling : $O(m^2 logC) = O(m^2)$

Shortest augmenting path : $O(m n^{1/2})$

 

 

Perfect matching

L, R상의 모든 노드가 matching에 참여해야함.

 

 

Hall's theorem

L의 어떠한 subset S를 잡았을 때, 거기에 해당되는 모든 matching을 N(S)라 하자. 이때 아래의 식이 항상 성립하면 perfect matching이다.

 

$|N(S)| \ge |S| $