koosaga's profile image

koosaga

February 15, 2022 00:00

Push Relabel Algorithm (1)

algorithm , graph theory

그래프의 최대 유량 (Maximum Flow) 를 찾는 문제는 웬만한 알고리즘 대회 입문서에는 다 소개되어 있는 중요한 문제이다. 일반적으로 최대 유량을 찾기 위해서는 Edmonds-Karp, Dinic과 같은 알고리즘을 사용한다. 이 알고리즘의 특징은 빈 그래프에서 시작해서 유량을 증가시키는 “증가 경로” 를 찾는 것을 반복하는 식으로 작동한다는 것이다. Dinic 알고리즘은 최악의 경우 $O(V^2E)$ 에 작동하지만 실제로는 이보다 훨씬 효율적으로 작동한다. 하지만 그럼에도 선형 시간에 가까울 정도로 빠르지는 않고, 한계가 분명히 있는 알고리즘이다.

이 글에서는 Push-relabel 이라고 하는 새로운 플로우 알고리즘을 설명한다. 예전에 유량 관련 알고리즘을 정리할 때도 간략하게 설명한 적이 있는 알고리즘인데, 해외 자료는 꽤 많은 데 비해 한국어 자료는 하나도 없어서 하나 만들게 되었다.

Push-relabel 알고리즘은 Dinic에 비해서 효율적이고, 다양한 효율적인 플로우 알고리즘의 기반이 된다 (예를 들어서 완전 다항시간 MCMF 등). 이론적으로 Push-relabel 알고리즘의 효용은 플로우 알고리즘에 한정되지 않으며 그래프 알고리즘 전반에 걸쳐서 아주 중요하다.

PS 기준으로는 Dinic만큼 중요한 알고리즘은 아니고, 몰라도 된다고 생각한다. 하지만 알고리즘이 생각보다 단순하고, 통상적인 유량 알고리즘과 완전히 색다른 접근법을 사용한다는데 의미가 있다. 가끔은 Maximum Flow로 시간 제한 안에 푸는 것이 의도되지 않은 문제를 억지로 푸는 데 사용될 수도 있고 성공 사례도 몇 번 봤다. 이론에서는 Push-relabel의 개념이 단순 플로우 문제 밖으로도 뻗어나가니 이 개념을 응용하지 않으면 못 푸는 문제가 나올 수도 있으려나… 잘 모르겠지만, 유량 관련 알고리즘에 관련이 있으면 배워 보는 것도 좋을 것 같다.

이 글에서는 독자가 기본적 플로우 개념과 Edmonds-Karp 알고리즘을 알고 있음을 가정한다.

1. 정의, 알고리즘의 개략적 작동 방식

방향 그래프 $G = (V, E)$ 와 source $s \in V$, sink $t \in V$ 가 있고, 각 간선에 대해서 용량 (capacity) $0 \le c(e)$ 가 있다고 하자. 각 간선 $e \in E$ 에는 Capacity가 $0$ 인 역변 $e^R \in E$ 가 있다. 올바른 flow 는 다음 조건을 만족한다.

  • $f(e) \le c(e)$
  • $f(e^R) = -f(e)$
  • source, sink 정점을 제외한 모든 정점에 대해서, 들어오는 간선의 $f$ 합과 나가는 간선의 $f$ 합이 같아야 한다. 달리 말해, 모든 $u \in V - {s, t}$ 에 대해서 $\sum_{(v, u) \in E} f(v, u) = \sum_{(u, v) \in E} f(u, v)$

이게 일반적으로 플로우 문제를 엄밀하게 정의하는 방법이다. 사실 디닉 알고리즘에 익숙해 있다면 위와 같은 정의, 특히 세 번째 정의가 그렇게 와닿지는 않는다. 디닉 알고리즘을 사용하면 위 세 번째 식이 당연히 성립하기 때문이다. 즉, 디닉 알고리즘은 $f(e) = 0$ 인 해부터 시작해서, 두 번째 조건을 절대 어기지 않으면서 계속 $f(e)$ 를 늘리는 방식이라고 이해할 수 있다.

이와 달리 Push-relabel algorithm은 중간 과정에서 세 번째 조건을 어긴다. Push-relabel algorithm에서는 preflow 라는 개념을 사용하는데, preflow는 다음 조건을 만족한다.

  • $f(e) \le c(e)$
  • $f(e^R) = -f(e)$
  • source, sink 정점을 제외한 모든 정점에 대해서, 들어오는 간선의 $f$ 합이 나가는 간선의 $f$ 합 이상이어야 한다. 달리 말해, 모든 $u \in V - {s, t}$ 에 대해서 $\sum_{(v, u) \in E} f(v, u) \geq \sum_{(u, v) \in E} f(u, v)$

즉, Push-relabel algorithm의 중간과정에서는 어떠한 정점에 대해서 들어오는 유량과 나가는 유량이 다를 수 있다 는 것이다. 이 때 이 차이를 초과량 (excess) 라고 정의하자. 정점 $u$ 의 초과량 $ex(u)$ 는 $\sum_{(v, u) \in E} f(v, u) - \sum_{(u, v) \in E} f(u, v)$ 로 정의된다. 편의상 여기서 역변은 세지 않는다. (역변을 세도 차이는 없으나 $ex(u)$ 의 값이 정확히 두 배가 된다. 없다 치는 것이 표현상 깔끔하다.)

만약 source, sink 정점을 제외한 모든 정점의 초과량이 0이면, preflow는 flow가 된다. 고로 알고리즘의 목표는 어떠한 preflow에서 시작해서, 초과량을 조금씩 줄여나간 후 최종적으로 flow에 도달하는 것이다. 이제 Push-relabel 알고리즘의 대략적인 작동 방식을 설명한다.

  • $ex(v) > 0$ 인 정점 $v$ 를 아무거나 잡는다.
  • $v$ 에서 나가는 잔여 용량이 0 초과인 간선을 아무거나 잡는다.
  • 이 간선의 유량을 $min(c(e) - f(e), ex(v))$ 만큼 증가시켜서 초과량을 간선 반대방향으로 보낸다.
  • 이 작업을 source, sink를 제외한 정점의 초과량이 0이 될 때까지 반복한다.

여기까지는 좋으나, 몇 가지 문제가 존재한다.

  • 초기 preflow는 어떻게 설정하는가?
  • 무한 루프를 돌지는 않는가?
  • 그래서 저게 flow를 찾는 것은 알겠으나, 그게 max flow가 되는가?

이 문제를 해결하기 위해서 각각의 정점에 높이 $h(v)$를 부여한다. 높이는 $0$ 이상 $V$ 이하의 정수인데, 높이 배정이 올바르다는 것은

  • $h(s) = V, h(t) = 0$
  • $e : u \rightarrow v$ 로 가는 간선의 잔여 용량이 있다면 ($f(e) < c(e)$) $h(u) \le h(v) + 1$

즉, $u$에서 $v$ 로 플로우를 흘려줄 수 있다면, $v$ 의 높이가 $u$ 보다 한 단계 낮거나, 그 이상이어야 한다. 각 정점이 실제로 높이가 있고, 플로우는 높은 곳 (source) 에서 낮은 곳 (sink) 로 물이 떨어지는 것이라고 상상하면 좋다. 실제 알고리즘에서도, 위에서 설명한 “초과량을 보내는” 연산을, $h(u) = h(v) + 1$ 인 $(u, v)$ 에 대해서만 적용할 것이다.

추가로, 만약에 정점에 올바른 높이를 배정할 수 있다면, $s$ 에서 $t$ 로 가는 augmenting path가 존재할 수 없다는 점을 확인하자. $s$ 에서 $t$ 로 가는 augmenting path가 존재한다면 이 경로의 간선은 $V - 1$ 개 이하인데, 경로를 이루는 각 간선이 높이를 최대 1 줄여주기 때문에 이러한 경로는 존재할 수 없다. Augmenting path가 존재하지 않는 flow는 Maximum flow이다. 고로, 항상 올바른 높이 배정이 되게끔 preflow를 설정해 주면, 알고리즘이 종료한 시점에는 그것이 max flow가 된다는 것이다.

이제 Push-relabel 알고리즘의 대략적인 작동 방식을 설명할 수 있다. 알고리즘은 초기에 올바른 preflow와 높이를 설정해 준다. 이후 초과량이 있는 정점이 있다면 이를 잡아서

  • 이보다 높이가 낮은 정점으로 보내주거나 (push)
  • 그것이 불가능하다면 높이를 다시 설정해 주거나 (relabel)

하는 것을 반복한다. 이 과정에서 항상 Preflow 조건과 높이 배정의 올바름은 유지되어야 한다. 이 알고리즘이 종료한다면, 높이 배정이 올바르기 때문에 알고리즘이 찾은 preflow가 최대 유량에 대응된다.

2. 알고리즘

알고리즘이 작동하기 위해서는 초기에 올바른 preflow와 올바른 높이 배정을 찾아야 한다. 만약 디닉 알고리즘처럼 $f(e) = 0$ 에서 시작한다면, 올바른 preflow이기는 하지만 augmenting path가 존재하여 올바른 높이 배정이 존재하지 않는다. 초기값은 다음과 같이 설정한다:

  • 소스에서 나가는 모든 간선 $(s, v) \in E$ 에 대해 $f(s, v) = c(s, v)$, 역변에 대해 $f(v, s) = -c(s, v)$. 나머지는 모두 $0$
  • $h(s) = V$, 나머지 정점에 대해서 $h(v) = 0$

각각이 올바른 preflow이고, 올바른 높이 배정임을 확인할 수 있다.

이제 알고리즘을 이루는 두 가지 연산, push 와 relabel을 설명한다.

  • push 연산은 $ex(u) > 0$ 인 임의의 source / sink가 아닌 정점 $u$에 대해서, 이 정점보다 높이가 낮은 정점으로 초과량의 플로우를 보내주는 연산이다. 즉, 만약 $e = (u, v)$ 에 대해 $h(v) = h(u) - 1$ 이고 용량이 남아있다면 ($f(e) < c(e)$) $f(e)$ 를 $min(c(e) - f(e), ex(u))$ 만큼 올려주는 것이다.
  • 만약 $ex(u) > 0$ 인 임의의 정점 $u$ 에 대해서 push 연산을 시행해 줄 수 있는 간선이 없다면, 이 정점을 relabel 시켜야 한다. relabel 연산은 단순히 $h(u)$ 를 1씩 증가시켜주는 연산이다.

이 두 연산을 해도 preflow 조건이 유지되며, 높이 배정 역시 올바르게 유지됨을 확인할 수 있다.

모든 준비가 끝났으니 Push-relabel 알고리즘을 설명한다. Push-relabel 알고리즘은 다음과 같이 작동한다:

  • 위에서 설명한 대로 초기 preflow와 높이를 설정.
  • $ex(u) > 0$ 이고 source/sink가 아닌 정점을 큐를 사용하여 관리.
  • 큐에서 $ex(u) > 0$ 인 정점을 뽑아서, push 연산이 가능할 때까지 relabel 한 후, push 연산 시행. 이 과정에서 새롭게 excess가 생긴 정점들을 큐에 추가.
  • 큐가 비면 알고리즘 종료.

이것이 Push-relabel 알고리즘이다.

3. 알고리즘의 증명

알고리즘은 항상 올바른 preflow와 높이 배정을 가지기 때문에, 알고리즘이 종료하는 시점에서 최대 유량을 찾음은 확인할 수 있다. 고로 우리는 알고리즘이 다항 시간의 연산 안에 종료함만 증명하면 된다.

이를 보이기 위해 몇 가지 Lemma들을 정리한다.

Lemma 1. 정점 $u \in V \setminus {s, t}$ 에 대해 $ex(u) > 0$ 일 경우 $u$ 에서 $s$ 로 가는 augmenting path가 존재한다. Proof. 귀납적으로 보일 수 있다. 초기 배정에서 이 성질이 성립함은 자명하다. push 연산을 사용할 경우 새롭게 excess가 생기는 정점 $v$ 에서 $u$ 로 residual edge가 생기고, $u$ 에서는 귀납 가정에 의해 $s$ 로 가는 경로가 존재한다. relabel 연산은 물론 상관 없다.

Lemma 2. 모든 정점에 대해 $h(u) \le 2V - 1$ 이다. Proof. $h(u)$ 가 증가한다는 것은 $ex(u) > 0$ 이라는 것이고 이는 Lemma 1에 의해 $s$로 가는 augmenting path가 존재한다는 뜻이다. augmenting path의 길이는 $V - 1$ 이하이고 path를 이루는 간선은 $h(i)$ 를 최대 1 줄일 수 있다.

Lemma 3. relabel 연산은 최대 $2V^2$ 번 수행된다. Proof. Lemma 2에 의해 자명하다.

push 연산은 두 종류로 나눈다. 만약 어떠한 push 연산 후 잔여 용량이 없다면 ($f(e) = c(e)$) 이를 saturating push, 그렇지 않다면 non-saturating push 라고 하자.

Lemma 4. Saturating push는 최대 $2VE$ 번 수행된다. Proof. 간선 $(u, v)$ 에 대해서 한번 saturating push가 일어났다는 것은 $h(u) = h(v) + 1$ 이었다는 것을 뜻한다. 이것이 다시 saturating push를 하기 위해서는 역변에 push가 일어나야 하고, 이는 $h(u) + 1 = h(v)$ 임을 뜻한다. 즉, 두 번 saturating push가 일어나면 $h(u)$ 가 최소 2 증가한다. Lemma 2와 조합하면 각 간선이 각 방향으로 최대 $V$ 번 saturating push된다는 것을 알 수 있다.

Lemma 5. Non-saturating push는 최대 $O(V^2E)$ 번 수행된다. Proof. 퍼텐셜 $\Phi = \sum_{u \in V \setminus {s, t}, ex(u) > 0} h(u)$ 로 정의하고, 이 값이 어떻게 변하는지 확인하자.

  • Relabel 연산은 $\Phi$ 값을 정확히 1 증가시킨다.
  • Saturating push 연산이 $e = (u, v)$ 에 일어났을 경우, $\Phi$ 값이 증가할 수도 있고 감소할 수도 있는데, 증가하는 경우는 $v$ 가 새롭게 $ex(v) > 0$ 이 되는 경우일 것이다. 고로 이 경우 최대 $2V - 1$ 증가한다.
  • Nonsaturating push 연산이 $e = (u, v)$ 에 일어났을 경우, $u$ 는 $ex(u) > 0$ 에서 $ex(u) = 0$ 이 되니 확실히 $h(u)$ 만큼 $\Phi$ 를 감소시킨다. $v$ 가 새롭게 $\Phi$에 기여할 수도 있지만, $h(v) - h(u) = -1$ 이니 어떠한 경우에도 $1$ 이상 감소한다.

Lemma 3, 4와 종합하면 $\Phi$ 는 Relabel / Saturating push 연산에 의해 최대 $2VE(V-1) + 2V^2 = O(V^2E)$ 만큼 증가한다. $\Phi$ 는 항상 0 이고, Nonsaturating push는 항상 $\Phi$ 를 1 이상 감소시키니, $\Phi$ 의 초기 값과 증가한 양의 합 이상 수행될 수 없고 고로 $O(V^2E)$ 번만 수행된다.

Theorem 6. Push-relabel 알고리즘은 최대 $O(V^2)$ 번의 relabel 연산과 최대 $O(V^2E)$ 번의 push 연산을 수행하고 종료한다.

Proof. Lemma 3, 4, 5에 의해 자명하다.

4. Push-relabel로 Minimum cut 구하기

Max-flow min-cut 정리에 의해서 그래프의 최대 유량은 최소 컷과 동일하다. 일반적인 플로우 알고리즘에서 최소 컷을 찾는 방법은, Residual graph에서 $s$ 에서 도달 가능한 정점 집합을 DFS로 찾는 방식이다. Push-relabel algorithm에서도 residual graph가 관리되니 이 방법을 사용하면 되겠지만, 알고리즘의 성질을 활용하여 조금 더 쉽게 최소 컷을 구하는 방법이 있다. Push-relabel이 단순히 최대 유량을 효율적으로 구하는 것에서 그치지 않는다는 사실을 이 예시를 통해서 이해하면 좋을 것 같다. (이 높이 배정이 일종의 Dual variable인 것 같은데, 무슨 LP인지는 정확히 잘 모르겠다.)

Lemma 7. $0 < i < V$ 에 대해서 $h(v) = i$ 인 정점이 없는 $i$ 가 존재한다. (이러한 $i$ 를 gap level 이라고 하자.) Proof. 모순을 가정하면 정점이 최소 $V + 1$ 개여야 한다.

Theorem 8. Gap level $g$ 에 대해 $S = {v h(v) > g}$ 라고 하자. $(S, V - S)$ 는 최소 컷이다. Proof. 올바른 높이 배정의 성질에 의해 $S$ 에서 $V - S$ 로 가는 간선들은 모두 포화되어 있다. Flow decomposition이 존재하기 때문에 그래프의 최대 유량을 경로들의 집합으로 분해할 수 있다. 이 경로는 $S$ 에서 $V - S$ 로 가고 다시 돌아오지 않는다. 만약 중간에 $V - S$ 에서 $S$ 로 돌아온다면, 역변이 포화되어 있지 않아서 가정에 모순이기 때문이다. 고로 포화된 간선의 가중치 합과 최대 유량 값은 동일하며 이는 $(S, V - S)$ 컷의 크기가 최대 유량과 동일함을 뜻한다.

5. 수행 시간 개선

Push-relabel 알고리즘의 시간 복잡도는 $O(V^2E)$ 이지만, 이 알고리즘의 시간 복잡도 내지는 수행 시간을 줄이려는 여러 시도가 있었다. 이 중 의미가 있는 최적화로 꼽을 것은 크게 네 가지가 있다.

  • FIFO: 새로운 Active vertex를 위에서 설명한 대로 큐에 저장하기만 해도 시간 복잡도가 $O(V^3)$ 이 됨을 증명할 수 있다.
  • FIFO + Link Cut Tree: 위 방법에 Link-cut tree를 결합해서 시간 복잡도가 $O(VE \log \frac{V^2}{E})$ 가 되게 할 수 있다. 이게 논문에 나온 오리지널 Push-relabel 알고리즘이다. 원 논문
  • Highest Label (HLPP): 새로운 Active vertex를 큐가 아닌 우선순위 큐에 저장하는데, 이 우선순위 큐는 Height가 가장 높은 정점을 반환한다. Height가 최대 $2V$ 정도이기 때문에 Heap과 같이 연산당 로그가 붙는 자료구조가 아니라 Bucket과 같은 방식으로 $O(1)$에 우선순위 큐를 관리할 수 있다. 이를 사용하면 시간 복잡도가 $O(V^2 \sqrt E)$ 가 됨을 증명할 수 있다.
  • Scaling: 각 간선의 최대 가중치가 $U$ 라고 하면, 초기 $\Delta = 2^{\lceil \log U \rceil}$ 이라는 값을 두고 이 값을 반씩 줄여가면서 알고리즘을 동작시킨다. 한 스테이지에서는, Height가 가장 작은 정점을 골라, 이 정점이 $ex(v) > \Delta / 2$ 를 만족하면, 다른 정점의 $ex(v) \le \Delta$ 를 만족하는 선에서 push 를 진행한다. 이 경우 한 Push는 $\Delta / 2$ 이상의 값을 흘리게 되어, 그래프가 일종의 Unit graph가 된다. 고로 각 스테이지가 $O(VE)$ 에 해결되고 (대충 모든 push가 saturating한다고 생각할 수 있음) 시간 복잡도가 $O(VE \log U)$ 가 된다.

여담으로 Dinic 알고리즘의 시간 복잡도가 $O(V^2E)$ 이고 이를 Link-Cut Tree로 최적화하면 $O(VE \log V)$ 가 됨을 기억하면 좋다. 우리가 Link-Cut Tree를 사용한 디닉 알고리즘을 사용하지 않는 것처럼, Theoretical한 bound가 중요하긴 하지만 실제 퍼포먼스는 더 중요하다.

그래서 어떤 최적화가 제일 빠를까? 몇 가지 참고 자료를 찾아보자.

  • LEMON 이라는 그래프 알고리즘 라이브러리에는 FIFO + LCT, HLPP가 구현되어 있다. 위 링크를 읽어보면, In most cases the Preflow algorithm provides the fastest method to compute the maximum flow, 즉 HLPP가 웬만하면 더 빠르다고 한다.
  • 이 코드포스 글 을 보면 LOJ Fastest 라는 알고리즘이 압도적으로 빠른 것을 확인할 수 있다. 해당 알고리즘은 HLPP에 이런 저런 휴리스틱을 많이 섞은 버전이다.
  • 해당 코드포스 글에 링크된 중국의 플로우 연습문제 의 Fastest submission을 확인해 보면 절대 다수의 코드가 비슷한 형태의 HLPP임을 알 수 있다.

내용들을 종합해보면 HLPP를 사용한 구현이 가장 효율적이라는 결론을 내릴 수 있다.

다음 내용은

다음 글에서는 HLPP를 사용한 Push-relabel 알고리즘의 간단한 구현, 그리고 Push-relabel에 기반한 다항 시간 MCMF 알고리즘 (Cost Scaling)에 대해서 다룰 예정이다.

참고 자료

  • e-maxx, Maximum flow - Push-relabel algorithm
  • https://www.cs.cmu.edu/~avrim/451f13/lectures/lect1010.pdf
  • https://ocw.mit.edu/courses/sloan-school-of-management/15-082j-network-optimization-fall-2010/lecture-notes/MIT15_082JF10_lec11.pdf
  • https://resources.mpi-inf.mpg.de/departments/d1/teaching/ws09_10/Opt2/handouts/lecture4.pdf