[Algorithm Part 2] 5. Mincut/Maxflow

이번 글에서는 mincut과 maxflow에 대해 살펴볼 것이다.

---

Mincut problem

source vertex(=s)와 target vertex(=t)를 가진 weighted digraph가 있을 때,

최소 capacity를 갖는 st-cut을 찾는 문제다.

직관적으로 말하자면, "s와 t를 최소 비용으로 분리시키는 cut"을 구하는 문제다.

Definition

A st-cut (cut) is a partition of the vertices into two disjoint sets, with s in one set A and t in other set B.

Its capacity is the sum of the weight(=capacities) of edges from A to B.

---

Maxflow problem

source vertex(=s)와 target vertex(=t)를 가진 weighted digraph가 있을 때,

최대값을 갖는 flow를 찾는 문제다.

직관적으로 말하자면, "t에 자원을 최대로 주는 flow"를 찾는 문제다.

Definition

An st-flow (flow) is an assignment of values to the edges such that:

• Capacity constraint: 0 ≤ edge's flow ≤ edge's capacity
• Local equilibrium(균형 유지?): inflow = outflow at every vertex (except s and t)

The value of flow is the inflow at t.

 

mincut과 maxflow는 서로 깊게 연관되어 있다!

---

Ford-Fulkerson algorithm

1. 모든 edge flow를 0으로 초기화한다.
2. augmenting path가 없을 때까지, 다음 과정을 반복한다.
   (즉, s에서 t까지의 모든 경로가 block될 때까지, 다음 과정을 반복한다.)
   
   1. augmenting path를 찾는다.
   2. bottleneck capacity를 계산한다.
   3. (bottleneck capacity를 사용해,) flow를 증가시킨다.

Definition

Augmenting path는 다음 2가지 조건을 만족하는 s에서 t까지의 무방향 경로다.

1. 모든 forward edge(s)의 flow가 non full이고
2. 모든 backward edge(s)의 flow가 non empty이다.

즉, augmenting path는 st-flow를 증가시켜주는 path다.

 

Augmenting path가 아닐 때, "s에서t까지의 경로가 block되었다"고 표현한다.

---

Relationship betweem flow and cut

Definition

The net flow across cut (A, B) is $\text{sum(A→B's flows)} - \text{sum(B→A's flows)}$.

1. Flow-value Lemma

Let $f$ be any flow and let (A, B) be any cut.

Then, $\text{net flow across (A, B)} = \text{value of } f$

 

flow-value lemma로 다음 명제를 추론할 수 있다.

outflow from s = inflow to t = value of flow

Proof (by 귀납법)

$B = \{t\}$일 경우,t의 outflow가 0이기 때문에, $\text{net flow across (A, B)} = \text{value of } f$임이 자명하다.

A의 임의의 원소 v를 B로 이동시켜도, local equilibrium로 인해, flow-value lemma이 유지된다.

2. Weak duality

Let $f$ be any flow and let (A, B) be any cut.

Then, $\text{value of }f\ \le \text{capacity of (A, B)}$

Proof

(Flow-value lemma를 이용하면 쉽게 증명할 수 있다.)

$\text{value of }f\ = \text{net flow across (A, B)} \le \text{capacity of (A, B)}$

3. Augmenting path theorem

A flow $f$ is a maxflow iff no augmenting paths.

4. Maxflow-mincut theorem

$\text{value of maxflow} = \text{capacity of mincut}$

Proof

모든 flow $f$에 대해, 다음 3개 명제는 동치(equivalent)다.

1. $\text{value of }f\ = \text{capacity of (A, B)}$인 cut (A, B)가 존재한다.
2. $f$는 maxflow다.
3. $f$에는 augmenting path가 없다.

1→2

(weak duality를 통해 쉽게 참임을 보일 수 있다.)

$\text{value of }f\ = \text{net flow across (A, B)} \le \text{capacity of (A, B)}$이므로,

$\text{value of }f\ = \text{capacity of (A, B)}$이면, $f$는 maxflow다.

2→3

augmenting path theorem에 의해, 자명하다.

3→1

$f$에는 "augmenting path가 없음"은, "s에서 t까지의 모든 경로가 blocked되었음"을 의미한다.

s에서 blocked되기 전까지의 모든 경로의 vertices를 A, 나머지를 B로 graph를 cut할 경우,

(A = non-empty backward edge 혹은 non-full forward edge만을 사용해 s와 연결된 vertices)

$\text{net flow across (A, B)} = \text{capacity of (A, B)}$가 된다.

A에서 B로 가는 foward edge(s)는 full이고,  B에서 A로 가는 backward edge(s)는 empty이기 때문이다. 

그러므로, $\text{capacity of (A, B)} = \text{value of }f$가 된다.

---

Compute mincut (A, B) from maxflow $f$:

"non-empty backward edge 혹은 non-full forward edge만을 사용해 s와 연결된 vertices"가 mincut의 A다.

---

Running time 

"FF algorithm이 maxflow와 mincut의 algorithm임"을 알았다.

그럼 FF algorithm으로 maxflow와 mincut을 구할 수 있는지 알아보겠다.

다시 말해, FF algorithm이 terminate(종료)되는지 알아보겠다.

(FF algorithm이 종료되지 않으면 maxflow와 mincut을 구할 수 없다.)

 

더 나아가, FF algorithm의 시간 복잡도에 대해 알아보겠다.

FF Algorithm 시간 복잡도의 핵심은 augmentation 횟수다.

---

Number of augmentation is finite?

우선 augmentation 횟수가 유한한지 알아보자!!

edge의 capacity가 1 ~ U 사이의 정수라고 가정하자.

1. Invariant

그럼, edge의 flow 또한 1 ~ capacity 사이의 정수다.

Proof

flow는 bottleneck capacity(=정수)만큼 증가/감소한다. 

Path의 임의의 edge가 full 혹은 empty가 될 때까지 flow를 증가/감소시키기 때문이다.

2. Proposition

augmentation 횟수 ≤ value of maxflow

즉, augmentation 횟수는 무조건 value of maxflow보다 작거나 같아야 한다.

 

 위 명제로 다음 명제를 추론할 수 있다.

value of maxflow가 유한하기에, augmentation 횟수는 유한하다.

Proof

각 augmentation는 적어도 value of flow를 1 이상 증가시킨다. (by invariant)

3. Integrality theorem

integer-valued maxflow가 존재한다.

Proof

FF로 maxflow를 구할 수 있다. (by proposition)

flow가 정수다 (by invariant)

---

Worst case

매우 불행하게도, augmentation 횟수가 value of maxflow가 될 수 있다.

하지만, 무작위로 augmenting path를 선택하지 않고,

특정 기준으로 augmenting path를 선택하면, worst case를 쉽게 피할 수 있다.

Way to choose augmenting paths

augmenting path	number of paths	implementation
shorest path	$\le 1/2EV$	queue(BFS)
fasttest path	$\le E\ln(EU)$	priority queue
random path	$\le EU$	randomized queue
DFS path	$\le EU$	stack(DFS)

shortest path: fewest number of edges

fasttest path: maximum bottleneck capacity

 

여기서 강조하고 싶은 것은, 위의 upper bound는 매우 보수적인 수치다.

실제는 upper bound에 근접하는 경우는 매우 드물고, 이보다 훨씬 적은 횟수로 끝난다.

---

Modeling flow network 

문제를 쉽게 풀기 위해, flow network를 residual network로 추상화(=abstraction)한다.

• flow network augmenting path = residual network directed path
• flow edge: two residual edge(forward edge, backward edge)
  • forward edge: residual capacity = $c_e - f_e$, augment flow = add the flow
  • backward edge: residaul capacity = $f_e$, augment flow = substract the flow

 

flow edge의 forward edge와 backward edge는 서로 동기화(flow, residual capacity)를 해줘야 한다!!

예를 들어, 임의의 forward edge가 residual network 경로에 사용되고 flow가 증가되어, residual capacity가 수정되면,

연관된 backward edge의 flow 증가분 만큼. residual capacity를 수정해야 한다.

---

Ford-Fulkerson algorithm

1. augmenting path를 찾는다. 즉, residual network의 directed path를 찾는다.
   (by, BFS using edgeTo[], visited[])
2. bottleneck capacity를 찾는다. 즉, 경로 edge의 최소 residual capacity를 찾는다.
3. bottleneck capacity로 경로 edge의 flow와 value of flow를 수정한다.
   즉, bottleneck capacity로 flow, residual capacity 그리고 value of flow를 수정한다.
4. augmenting path가 없을 때까지, 반복한다.

이때, 최종 value of flow와 visited가 각각 maxflow와 mincut의 solution다.

(최종 visited는 augmenting path가 없는 상황에서, vertex s로부터 방문한 모든 vertex다.)

---

Application

maxflow, shortest path 같은 문제는 광범위하게 사용되는 문제 (해결) 모델(=general problem solving model)다.

즉, 수 많은 문제를 위와 같은 문제로 재구성하여 풀 수 있다.

General Problem Solving Problem 조건은 2가지가 있다.

1. 문제가 일반적이다. 즉, 재구성하기 좋게, 문제가 일반적으로 정의되어야 한다.
2. 효율적인 알고리즘이 존재한다.

---

1. Bipartite matching problem

N명의 구직자와 N개의 채용공고(=한 사람만 채용하는 채용공고)가 주어졌을 때,

"모든 구직자가 고용되는 경우의 수"를 찾는 문제다.

 

추상적으로 설명하자면, "bipartite graph가 주어졌을 때, prefect matching 찾는 문제"다.

Definition

Bipartite graph:

• 2개 vertices 집합(S, T)을 가지고 있다. (e.g., S: 구직자, T: 채용 공고)
• 모든 edge는 한 집합의 vertex $v$에서 다른 집합의 vertex $w$로 이동한다.
  (e.g., 구직자가 채용에 합격했을 경우에만, edge를 추가한다.)

 

Matching in the graph: 서로 만나지 않는(=공유하는 vertex가 없는) edges의 집합 

Modeling (or Abstract)

Bipartite graph을 flow network으로 다음과 같이 추상화(=abstraction)한다.

• s, t vertices를 생성한다.
• s에서 S's vertex로 가는 edge(s→S's vertex)를 추가한다. (capacity = 1)
• T's vertex에서 t로 가는 edge(T's vertex→t)를 추가한다. (capacity = 1)
• S's vertex에서 T's vertex로 가는 edge(S's vertex→T's vertex)를 추가한다. (capacity = ∞)

 

이렇게 만들어진 flow network의 maxflow를 구한다. (by FF algorithm)

maxflow가 N이 나오면, perfect matching이 존재하는 것이며, N이 나오지 않으면, 존재하지 않는 것이다.

 

만약 perfect matching이 존재하지 않는다면, 왜 그런지 mincut으로 설명해보자!!

flow network의 mincut (A, B)가 있을 때,

$S_a$를 S's vertex of A set, $T_a$를 T's vertex of A set라고 가정한다,

이때, $S_a$는 오직 $T_a$만 matching할 수 있다.

때문에,  $|S_a| > |T_a|$이면, 당연히, perfect matching이 안된다.

---

2. Baseball elimination

최다 승수를 가진 팀이 리그 우승을 한다고 가정할 시,

현재 우승 경쟁이 가능한 팀들과 아닌 팀들을 구별하는 문제다.

특정 팀이 우승 경쟁 여부를 구하는 문제로 단순화 해보겠다.

 

이때, 현재 승수와 잔여 경기 수 뿐만 아니라, 잔여 경기의 상대도 중요한 요소다.

Modeling (or Abstract)

위 문제(특정 팀(=A팀)의 우승 경쟁 여부)를 flow network으로 다음과 같이 추상화(=abstraction)한다.

• s, t vertices를 생성한다.
• game vertices(e.g., B-C: B팀과 C팀의 경기)와 team vertices(e.g., B: B팀)를 생성한다.
  (이때, A팀과의 game vertices, A팀의 team vertex는 제외한다. A팀은 잔여 경기를 이긴다고 가정할 거다.)
• s에서 game vertex로 가는 edge(s→game's vertex)를 모두 추가한다. (capacity = 잔여 경기 수)
• team vertices에서 $t$로 가는 edge(team's vertex→t)를 모두 추가한다. (capacity = A팀의 최대 예상 승수 - 팀의 현재 승수)
• game vertex에서 team vertex로 가는 edge((game's vertex→team's vertex)를 추가한다. (capacity = ∞)

 

이렇게 만들어진 flow network의 maxflow를 구한다. (by FF algorithm)

이때, s에서 game vertex로 가능 모든 edge가 full인 경우 

즉, mincut(A, B)가 있을 때, A에 s만 존재할 시, A팀은 "우승 경쟁 가능"을 의미한다.

다시 말해, 임의의 game vertex가 non-full일 경우, "우승 경쟁 불가능"을 의미한다.

왜냐하면, 팀A가 모든 경기를 이겨도, 임의의 팀이 무조건 그보다 많은 승수를 가져기기 때문이다.

(직관적으로 이해가 어렵기에, 고찰해보시기 바란다.)