koosaga's profile image

koosaga

April 17, 2022 00:00

Push Relabel Algorithm (2)

algorithm , graph theory

2월의 Push-Relabel algorithm 관련 글에 이어서 Push-relabel에 기반한 다항 시간 MCMF 알고리즘 (Cost Scaling)에 대해서 다룰 예정이다. 이 글에서는 일반적으로 알려진 Successive Shortest Path Algorithm보다 훨씬 더 효율적인 알고리즘을 다룬다.

MCMF (Minimum-Cost Maximum-Flow) 문제는 알고리즘 대회 입문서에 다 소개되어 있는 중요한 문제이다. 2월 중순에 글이 올라온 뒤, 3월 1일 Almost-Linear Time Minimum Cost Flow 가 가능하다는 사실이 알려져서 많은 화제를 모았다. 당연하지만 이론전산에서 아주 중요한 연구 결과이고, 저자들은 아마 권위있는 상 하나 정도는 수상하지 않을까 싶다. 우리가 대회에서 흔히 사용하는 Successive Shortest Path Algorithm은 꽤 비효율적인 알고리즘에 속하는데, 위 논문에서는 놀랍게도 이러한 문제가 (이론적으로라도) 준 선형 시간에 해결하는 알고리즘을 제시하기 때문이다.

이번 시리즈에서 다루고 있는 알고리즘들은 이론적으로나 실용적으로나 효율적인 플로우 알고리즘들의 기초가 된다. 현재까지 알려진 가장 실용적인 효율적인 플로우 알고리즘들이 모두 Push-relabel에 기초해 있고, 위 논문에 나와 있는 이론적인 알고리즘을 이해하는 데 기본이 되기 때문이다 (다만 논문에 있는 알고리즘이 Push-relabel은 아니다).

PS 기준으로 생각했을 때, Successive Shortest Path Algorithm(SSP) 의 시간 복잡도는 벨만-포드를 사용할 경우 $O(fVE)$ 이다. 고로 $f$ 가 커질 경우 다항 시간 알고리즘이 아니다 (pseudo-polynomial). 하지만 오늘 다루게 될 알고리즘의 시간 복잡도는 $O(V^3 \log (VC))$ 정도의 시간 복잡도에 작동하는 다항 시간 알고리즘이다. 고로 플로우의 케이스와는 다르게 Push-relabel을 사용한 MCMF는 대회에서도 충분히 나올 수 있다. 상당히 심화된 경우일 테니 일반적인 경우에는 볼 일이 없겠지만, 대회에 나온 사례가 존재하는 것 자체는 사실이다 (1 2).

다만 카이스트 2021 가을대회 L. Utilitarianism 2 처럼 SSP로만 풀 수 있는 MCMF도 존재해서, SSP의 상위호환이라는 결론은 성급하다고 생각한다. 만약 augmenting path의 개수가 매우 작거나 shortest path가 (벨만 포드 등 없이) 효율적으로 구해진다면, 물론 SSP가 Cost Scaling보다 효율적이다.

이 글에서는 독자가 Part 1의 글을 이해하고 있으며 MCMF 문제를 Cycle Canceling + Dijkstra를 사용한 SSP로 해결할 수 있다고 가정한다. 즉 독자는 각 정점에 potential 을 주어서 음수 간선을 지우는 테크닉을 이해하고 있어야 한다. (카이스트 2021 가을대회 L. Utilitarianism 2 참조)

1. 정의와 기초적 성질

이 글에서는 Minimum Cost Flow의 일반화된 문제인 Minimum-Cost Circulation 문제를 다룬다. Circulation의 특징은 source와 sink가 따로 없으며, 유량에 하한이 있을 수 있다는 점이다. 이전 글에서도 소개한 바 있지만 사실 Circulation과 Flow는 동치이며, Flow를 풀 수 있다면 Circulation도 풀 수 있고 그 반대도 가능하다. Circulation 형태로 표현해야 알고리즘이 자연스럽게 나오기 때문에 이 글에서는 이러한 설명을 따른다.

Definition. Minimum-Cost Circulation Problem 에서는

  • 입력으로
    • Directed Graph $G = (V, A)$ 가 주어진다.
    • 모든 간선 $(i, j) \in A$ 에는 가중치 $c_{i, j}$ 가 있다.
    • 모든 간선 $(i, j) \in A$ 에는 용량 상한 $u_{i, j}$ 가 있고
    • 모든 간선 $(i, j) \in A$ 에는 용량 하한 $l_{i, j}$ 가 있다. ($l_{i, j} \le u_{i, j}$)
  • 목표는, 각 간선에 대해서 Circulation $f_{i, j}$ 를 찾아서 $\sum_{(i, j) \in A} c_{i, j} f_{i, j}$ 를 최소화하거나, 해가 없음을 반환하는 것이다. 이 때 Circulation은
    • $l_{i, j} \le f_{i, j} \le u_{i, j}$ 를 만족하며 (용량 제한 조건)
    • $\sum_{k:(i, k)\in A} f_{i, k} - \sum_{k:(k, i)\in A} f_{k, i} = 0$ 이 모든 정점에 대해 만족해야 한다. (유량 보존 조건)

Circulation은 Flow가 동치이고, 우리는 효율적인 플로우 알고리즘을 배웠기 때문에, 다음과 같은 사실을 관찰할 수 있다.

Lemma 1. 해의 존재 여부는 한 번의 Maximum Flow 연산으로 $O(V^2 \sqrt E)$ 에 판별할 수 있다.

이후 표현의 간결함을 위해서 간선의 용량 하한을 직접 표현하는 대신, 역변에 음수 상한이 가해진 것 으로 해석한다. 즉, 정변의 용량은 $u_{i, j}$ 이고, 역변의 용량은 $-l_{i, j}$ 라서, 역변에 $-l_{i, j}$ 초과의 플로우가 흐르고 있다면 (즉 정변의 플로우가 적다면) 용량을 초과하는 것이다. 유사하게, 역변의 가중치는 정변의 가중치에 $-1$을 곱한 것, 즉 $c_{j, i} = -c_{i, j}$ 이다.

어떠한 Flow가 Maximum이라는 것은, source에서 sink로 가는 augmenting path가 없다는 것과 동치이다. 유사하게, 어떠한 Circulation이 Optimal하다는 것을 다음과 같이 표현할 수 있다. Flow와 마찬가지로 $f_{i, j} < u_{i, j}$ 라면 이를 residual edge 라고 하자.

Claim. Residual edge만으로 이루어진 음수 사이클이 없다면 해당 circulation은 optimal하다.

음수 사이클이 없는 그래프에는 정점에 퍼텐셜을 주어서 음수 간선을 지울 수 있다. 달리 말해, 함수 $p : V \rightarrow \mathbb{R}$ 이 존재하여 모든 residual edge $(i, j)$ 에 대해 $c_{i, j} + p_i - p_j \geq 0$ 이다. 음수 사이클이 있는 그래프에는 퍼텐셜이 존재할 수 없으니, 퍼텐셜의 존재 여부와 음수 사이클의 존재 여부는 동치이다. 이 점을 사용하여 Lemma 2를 다시 풀어보면 다음과 같다.

Claim. 모든 residual edge $(i, j)$ 에 대해 $c_{i, j} + p_i - p_j \geq 0$ 인 퍼텐셜 함수 $p : V \rightarrow \mathbb{R}$ 이 존재한다면 해당 circulation은 optimal하다.

이제 $c_{i, j}^p = c_{i, j} + p_i - p_j \geq 0$ 라고 하자. $c, c^p, f$ 는 이제 벡터라고 생각하고, 최소화하는 함수도 간결하게 $c \cdot f$ 라고 표현한다. 여기서 $c \cdot f = c^p \cdot f$ 임을 관찰하자.

이제 위 두 Claim을 증명한다.

Theorem 2. 다음 세 명제는 모두 동치이다.

  • circulation이 optimal하다.
  • Residual edge만으로 이루어진 음수 사이클이 없다.
  • 모든 residual edge $(i, j)$ 에 대해 $c_{i, j} + p_i - p_j \geq 0$ 인 퍼텐셜 함수 $p : V \rightarrow \mathbb{R}$ 이 존재한다.

이제 세 명제의 동치 관계를 증명한다.

  • $1 \rightarrow 2$: 대우명제를 증명하는 것이 간단하다. 음수 사이클이 있다면 circulation에 이 음수 사이클을 추가해 줌으로써 비용을 줄일 수 있다.
  • $2 \rightarrow 3$: 글을 읽는데 이미 필요한 사전지식이니 여기서 증명하지 않는다.
  • $3 \rightarrow 1$: 귀류법을 사용한다. 만약 더 좋은 circulation $f^$ 가 존재한다고 하자. $f^ - f$ 는 용량 제한 조건은 만족하지 않겠지만 유량 보존 조건을 만족하는 circulation이다. 가정에 따라 $c \cdot (f^* - f) < 0$ 이다. 이에 따라 $c^p \cdot (f^* - f) < 0$ 이다. $f^_{i, j} - f_{i, j} > 0$ 이라면, $f_{i, j} < u_{i, j}$ 니 $c_{i, j}^p \geq 0$ 이다. 고로 $c^p \cdot (f^ - f) = \sum_{(i, j) \in A, f_{i, j} > 0} c_{i, j}^p f^\prime_{i, j} + \sum_{(i, j) \in A, f_{i, j} < 0} c_{j, i}^p f^\prime_{j, i} = 2\sum_{(i, j) \in A, f_{i, j} > 0} c_{i, j}^p f^\prime_{i, j} \geq 0$ 임으로 가정에 모순이다.

이를 토대로 우리는 Naive한 알고리즘을 유도할 수 있다. Circulation을 맨 처음 이야기한 것처럼 플로우 알고리즘으로 찾은 후, 음수 사이클을 $O(nm)$ 에 벨만 포드로 찾은 후 계속 추가해 주는 것이다. 이 알고리즘이 종료한다는 사실은 쉽게 증명할 수 있으나 딱히 다룰 필요는 없으니 생략한다.

이렇게 반복적으로 음수 사이클을 제거하는 Naive한 알고리즘은 우리가 알고 있는 SSP Algorithm과 동일하다는 것을 알 수 있다. MCMF를 Circulation으로 변환하기 위해서는 sink에서 source로 가는 무한한 가중치의 간선 하나만 추가해 주면 된다. 초기 MCMF 모델링에 음수 사이클이 없다면 (일반적으로 제대로 된 MCMF 모델링에는 음수 사이클이 없다) 음수 사이클은 sink -> source로 가는 무한한 가중치의 간선을 사용할 수 밖에 없다. sink -> source로 가는 간선을 사용하는 음수 사이클은, source -> sink로 가는 최단 경로와 동일하다. 고로 이 나이브한 알고리즘이 우리가 익히 알고 있는 SSP MCMF 알고리즘이라고 생각하면 된다.

2. Minimum mean-cost cycle canceling

위 Naive한 알고리즘에서, 우리는 아무 사이클이나 제거해도 항상 알고리즘이 종료하며 최적해를 찾는다는 것을 배웠다. 이 사이클의 선택만 더 효율적으로 바꿔줘도 다항 시간 알고리즘을 얻을 수 있다. 지금 소개할 Minimum mean-cost cycle canceling 알고리즘은 이후 소개할 Cost Scaling에 비해서 이론적으로나 실용적으로나 상당히 비효율적으로, 알고리즘 자체가 중요하지는 않으나 시간 복잡도 분석 과정이 중요하기 때문에 배울 가치가 있다.

Definition 3. 사이클 $C$ 의 평균 비용을, 사이클의 가중치 합을 사이클의 간선 개수로 나눈 값으로 정의한다.

Theorem 4. 평균 비용을 최소화하는 사이클 (minimum mean-cost cycle) 을 $O(nm)$ 시간에 찾을 수 있다. Proof. https://koosaga.com/189 의 B. Cycle Mean 단락을 참고하라. Theorem 4의 증명을 몰라도 글을 읽는데 아무 지장 없으니 관심 없으면 넘어가도 된다.

이제 그냥 음수 사이클이 아닌 평균 비용을 최소화하는 음수 사이클을 Theorem 4를 통해서 $O(nm)$ 에 찾으면, Minimum mean-cost cycle canceling 알고리즘이 정말 간단하게 완성된다.

이제 가장 중요한, 이 알고리즘의 시간 복잡도를 분석한다. 크게 두 가지 방법이 있고, 방법에 따라 다른 시간 복잡도가 나온다. $T_{mean}(n, m)$ 은 minimum mean-cost cycle을 찾는 데 드는 시간으로 Theorem 4에 의해 $T_{mean}(n, m) = O(nm)$ 이다.

  • Goldberg-Tarjan 의 $O(mn \log (nC) * T_{mean}(n, m))$
  • Tardos의 $O(m^2 n \log n * T_{mean}(n, m))$

이 글에서는 이 두 증명을 모두 소개한다.

2.1. Bounds by Goldberg-Tarjan

Goldberg-Tarjan 의 증명은 이후 Cost Scaling을 이해하는데 필요하니 꼭 익혀두자.

Definition 5. Circulation $f$ 가 $\epsilon$-optimal 하다는 것은 $c_{i, j}^p \geq -\epsilon$ 을 만족하는 퍼텐셜 함수 $p$ 가 존재함과 동치이다.

$C = \max_{e} C_e$ 라고 하자. 모든 Circulation은 $C$-optimal 하고 ($p = 0$), Min-cost Circulation은 $0$-optimal하다 (Lemma 2).

Definition 6. $\mu(f)$ 를 Circulation $f$ 에 대한 Minimum mean-cost cycle의 평균 비용으로 정의하자. Definition 7. $\epsilon(f)$ 를 Circulation $f$가 $\epsilon$-optimal할 수 있는 퍼텐셜이 존재하는 최소 $\epsilon$ 로 정의하자.

두 값은 전혀 상관 없어 보이지만…

Theorem 8. $\mu(f) = -\epsilon(f)$. Proof. 평균이 $X$ 미만인 사이클이 존재한다는 것은, 모든 간선의 가중치를 $X$ 씩 줄였을 때 음수 사이클이 존재한다는 것과 동치이다. 고로, 모든 간선의 가중치를 $\mu(f)$ 만큼 줄일 경우 (음수만큼 줄이니까 늘어난다), 음수 사이클은 없지만 가중치가 정확히 0인 사이클은 존재할 것이다. 이 그래프에서의 퍼텐셜을 구하면 그게 원래 그래프에서 $-\mu(f)$ optimal한 퍼텐셜이 되고, 가중치가 0인 사이클 때문에 이보다 좋은 퍼텐셜은 존재하지 않는다. $\blacksquare$

Circulation $f$에 대해서, $f^k$ 를 해당 circulation에서 min mean-cost cycle을 $k$ 번 cancel한 후 결과라고 하자. 다음과 같은 사실이 참이다.

Theorem 9. $\epsilon(f^1) \le \epsilon(f)$ Proof. 가정에 의해 $c_{i, j}^{p} \geq -\epsilon(f)$ 인 퍼텐셜 $p$ 가 존재한다. minimum mean cost cycle을 $C$ 라고 하면, $c_{i, j}^{p}$ 의 가중치 합은 $C \mu(f) = -C\epsilon(f)$ 이다. 사이클 상에서 $c_{i, j}$ 의 합은 $c^p_{i, j}$ 의 합과 같으니 이는 $C$ 의 모든 간선에 대해 $c_{i, j}^{p} = -\epsilon(f)$ 가 성립함을 뜻한다. 이제 $f^1$ 에서 퍼텐셜 $p$ 가 $-\epsilon(f)$ 함을 보여야 하는데 이는 간단하다. 일단 정변의 $c^p_{i, j}$는 변할 수 없다. 역변의 경우 $c^p_{j, i} = -c^p_{i, j}$ 임을 관찰하면, $\epsilon(f) \geq -\epsilon(f)$ 라서 원래 조건을 위배하지 않는다. $\blacksquare$

Theorem 10. $\epsilon(f^{m+1}) \le (1 - 1/n) \epsilon(f)$ Proof. 초기 $\epsilon(f)$-optimal한 퍼텐셜을 $p$ 라고 하자. 두 가지 경우가 있다.

  • Case 1. Cancel한 사이클에서 $c_{i, j}^p$ 가 모두 0 미만이다. 이 경우 Cancel 이후 최소 하나의 음수 간선이 제거되지만, 새로 생기는 역변들은 모두 양수이다. 그래프에 음수 간선은 최대 $m$ 개이니 Case 1이 연속해서 $m+1$ 번 이상 등장할 수 없다.
  • Case 2. Cancel한 사이클에 $c_{i, j}^p$ 가 0 이상인 간선이 있다. $C$ 를 그러한 사이클이라고 하고, 이게 $k$ 번째 iteration이라고 하자. 사이클의 평균 비용은 $\mu(f^k) = \frac{\sum_{(i, j) \in C} c^p_{i, j}}{C} \ge \frac{(C - 1) (-\epsilon(f))}{C} \geq (1 - 1/n) (-\epsilon(f))$이다. Theorem 8과 결합하면 $\epsilon(f^k) \le (1 - 1/n) \epsilon(f)$ 가 성립한다. Case 1의 성질에 의해, $m+1$ 번 사이클을 Cancel하면 그 중 한번은 Case 2가 일어난다. $\blacksquare$

Theorem 10에 의해, 평균 비용을 최소화하는 사이클을 반복적으로 cancel할 경우, 특정 횟수의 반복마다 $\epsilon(f)$ 가 상수배씩 줄어든다. 이제 이를 사용해서 알고리즘을 증명하는 것은 쉽다.

Observation 11. $\epsilon(f) < 1/n$ 일 경우 $f$ 는 optimal circulation이다. Proof. $\epsilon(f) < 1/n$ 인데 optimal하지 않은 경우, 가중치가 $0$ 미만 $1/n$ 초과인 음수 사이클이 존재하는데 정수에서 이는 불가능하다.

Theorem 12. Minimum mean-cost cycle canceling 알고리즘은 최대 $O(mn \log(nC))$ 번 사이클을 cancel한 후 종료한다. Proof. 초기 circulation은 $C$-optimal하다. $k = mn \log (nC)$ 번 cancel을 반복하면, $\epsilon(f^k) \le (1 - 1/n)^{n \log (nC)} C \le e^{-\log(nC)}C = 1/n$ 이다.

2.2 Bounds by Tardos

Tardos의 증명의 경우 $O(m^2 n \log n)$ 번의 cancel 이후 종료함을 증명하며, 실질적으로 2.1의 증명보다 훨씬 더 큰 상한을 보인다고 보는 것이 맞다. 하지만 Goldberg-Tarjan의 경우 가중치인 $C$ 에 대한 log-dependency가 붙는다. log에 비례하기 때문에 다항 시간 알고리즘은 맞다. 하지만 입력으로 들어온 정수의 크기가 어떻던간에 사칙 연산의 횟수가 다항 시간번이어야 하는 strongly polynomial 알고리즘은 아니다. 유클리드 알고리즘, 선형 계획법의 경우가 다항 시간에 풀리지만 strongly polynomial 이 아닌 대표적 예시이다.

Tardos의 증명은 Minimum cost circulation이 strongly polynomial 시간에 풀린다는 것을 처음 발견한 증명이다. 이는 당대 중요한 Open problem이었으며 이 업적으로 Tardos는 1988년 Fulkerson prize를 수상한다. 하지만 이 증명을 몰라도 Cost Scaling을 이해하는 데는 큰 지장이 없으니, 관심있는 사람만 읽어보면 될 것 같다.

바로 정의로 넘어가자.

Definition 13. 간선 $(i, j)$ 가 $\epsilon$-fixed라는 것은 모든 $\epsilon$-optimal circulation 에서 해당 간선을 흐르는 유량의 값이 같다는 뜻이다.

이 증명의 Main Theorem은 다음과 같다.

Theorem 14. $\epsilon > 0$ 에 대해서, circulation $f$ 의 $\epsilon$-optimal한 퍼텐셜을 $p$ 라고 하자. 만약 $c^p_{i, j} \geq 2n\epsilon$ 이면 $(i, j)$ 는 $\epsilon$-fixed 이다.

직관적으로 생각했을 때, 간선의 가중치가 극단적일 경우 알고리즘이 이 쪽으로 플로우를 몰아주든 피하든 더 많은 관심 을 받게 될 것이고 고로 일찍 그 유량을 결정할 수 있다는 것이다. Theorem 14를 이용한 증명의 흐름도 이와 동일하다. 사이클을 cancel하다 보면 점점 간선이 하나씩 $\epsilon$-fixed가 된다. Theorem 9에 의해 Cancel을 하는 과정에서 $\epsilon$ 이 늘어나는 일은 없다. 고로 한번 간선이 $\epsilon$-fixed가 된다면 앞으로 그 간선의 유량이 바뀌는 일은 없고, 해당 간선의 답을 찾았다 라고 생각할 수 있다. 이를 계속 반복하다 보면 모든 간선의 답을 찾게 되고 알고리즘이 종료하는 것이다.

이 흐름을 타고 가서, Theorem 14의 증명을 하기 전에, 최종 결과를 증명하자.

Theorem 15. Min mean-cost cycle canceling 알고리즘은 $O(m^2n \log n)$ 번 반복 후 종료한다. Proof. 현재의 $\epsilon$ 에 대해서, 한번 간선이 $\epsilon$-fixed가 되면, $\epsilon$ 이 비증가하기 때문에 영원히 $\epsilon$-fixed된다. 고로 $k = mn \log(2n)$ 번의 연산 이후 새로운 간선이 fixed됨을 증명하면 된다. 현재 circulation을 $f$, 여기서 찾는 사이클을 $C$ 라고 하자. Theorem 10에 의해서, $\epsilon(f^k) \le (1 - 1/n)^{n \log (2n)} \le \frac{\epsilon(f)}{2n}$ 이다. $\epsilon(f^k)$-optimal한 $f^k$ 에 대한 퍼텐셜을 $p^k$ 라고 하자. $p^k$ 기준으로 $C$ 를 볼 경우, $\frac{\sum_{(i, j) \in C} c^{p^k}{i, j}}{C} = \mu(f) = -\epsilon(f) < -2n\epsilon(f^k)$ 이다. 고로 해당 사이클에 $c^{p^k}{i, j} < -2n\epsilon(f^k)$ 인 간선 $(i, j)$ 가 존재해야 한다. Theorem 14에 의해 이 간선은 $\epsilon(f^k)$-fixed 된다. $\blacksquare$

결국 요지는, circulation의 $\epsilon$ 은 계속 감소할 것이고, 그 과정에서 초기에 Cancel된 사이클에 속한 간선들 (즉, mean을 낮추는 데 기여한, 가중치 절댓값이 큰 간선들) 은 $\epsilon$이 감소하면서 $\epsilon$-fixed 상태로 전향한다는 것이다.

이제 Theorem 14의 증명만 하면 된다. 증명을 간략히 요약하자면, $-2n \epsilon$ 이하의 가중치를 간선이 있고 이 간선의 유량이 다를 수 있다면, $-\epsilon$ 미만의 평균 가중치를 가지는 사이클을 찾을 수 있어서 가정에 모순이라는 것이다.

Observation. 임의의 circulation $f$ 와 $S \subsetneq V$ 에 대해서 $\sum_{k \in S, l \neq S} f_{k, l} = 0$ 이다. (Circulation이기 때문에 임의의 부분집합에 들어가는 양과 나가는 양은 동일하다.)

Theorem 14의 증명. 귀류법을 사용한다. $f^\prime$ 을 $f^\prime_{i, j} \neq f_{i, j}$ 인 가정에 모순인 circulation 이라고 하자. 또한 $c_{i, j}^p \le -2n\epsilon$ 이라고 하자 (이래도 일반성을 잃지 않는다. 만약 양수면 $i, j$ 를 스왑해서 생각하자).

$c_{i, j}^p \le -2n\epsilon$ 이고 $f$가 $\epsilon$-optimal하기 때문에, $(i, j)$는 $f$ 에 대해 residual edge가 아니다. 고로 $f_{i, j} = u_{i, j}$ 이고 $f^\prime_{i, j} < f_{i, j}$ 이다. 이제 $f - f^\prime$ 이라는 circulation을 생각하자. $S$ 를 이 circulation에서 $j$ 번 정점을 시작으로 방문할 수 있는 정점의 집합이라고 하자. 만약 $i \notin S$ 라면, $S$ 에서 $V - S$ 로 나가는 $f - f^\prime$ 상 유량 있는 간선은 없다. 한편 $i \rightarrow j$ 로 가는 유량 있는 간선이 있으니, $S$ 로는 들어오는 유량은 있지만 나가는 유량은 없고 유량이 보존되지 않는다.

고로 $i \in S$ 이고 $f - f^\prime$ 에는 $(i, j)$ 를 포함하는 사이클이 있다. 이에 따라 $f^\prime$ 의 residual edge만을 사용하며 $(i, j)$ 를 포함하는 사이클 역시 있다. 이 사이클을 $C$ 라고 하자.

$C$ 에 있는 간선 $(k, l)$ 에 대해, $f_{l, k} < f^\prime_{l, k} \le u_{l, k}$ 가 만족한다 ($k, l$이 뒤바뀜에 유의). 고로 $(l, k)$ 는 $f$ 의 residual edge이고 $c_{l, k}^p \geq -\epsilon$ 이다. 고로 $c_{k, l}^p \le \epsilon$ 이다. 그렇다면

$\mu(f^\prime) \le \frac{\sum_{(i, j) \in C} c^p_{i, j}}{C} = \frac{1}{C} (c_{i, j}^p + \sum_{(k, l) \in C \setminus {(i, j)}} c_{k, l}^p) \le \frac{1}{C}(-2n\epsilon + (C - 1) \epsilon) < -\epsilon$

으로 가정에 모순이다. $\blacksquare$

3. Cost Scaling

Cost Scaling 알고리즘은 Min cost circulation 문제를 $O(n^3 \log (nC))$ 시간에 해결하는 아주 효율적인 알고리즘이다.

이론적으로, (Almost linear MCMF를 논외로 두더라도) Cost Scaling보다 빠른 MCMF는 여러가지 있다. 예를 들어서, Cost가 아닌 Capacity를 scale하는 Capacity Scaling의 경우 $O(m \log U)$ 번의 Dijkstra 계산으로 문제를 해결한다. 고로 시간 복잡도가 $O(m \log U (n \log m + m))$ 으로 Sparse한 그래프에서 Cost Scaling보다 효율적이다. 또한 Link cut tree 등의 자료구조를 사용하면 $O(nm \log n \log (nC))$ 시간에 Cost Scaling을 구현할 수도 있으며 이 역시 Sparse한 그래프에서 더 효율적이다. 하지만 아래 참고 자료 문단에서 확인할 수 있는, 논문 및 온라인 저지 상의 벤치마크들을 볼 경우, 실제로는 $m = 8n$ 정도의 sparse한 그래프에서도 Cost scaling이 Capacity scaling보다 훨씬 더 빠른 성능을 보여주며, 약간의 이론적 이점이 실질적인 성능 향상으로 연결되지 않음을 보여준다. 고로 이 글에서는 기본적인 형태의 Cost Scaling만 소개하고, 다른 알고리즘은 소개하지 않는다.

Cost scaling의 optimization 전략은 간단하다. 기존의 Cycle canceling은 $O(m)$ 번 사이클을 cancel할 경우 $\epsilon$ 이 $(1 - 1/n)$ 배 줄어든다. 당연하겠지만, 한 번의 연산으로 $\epsilon$ 을 반으로 줄이는 서브루틴이 존재한다면 위 논의에 의해 $O(\log (nC))$ 번만 해당 서브루틴을 실행해도 답을 찾을 것이다. Cost scaling의 핵심은 이러한 서브루틴이 존재하고 $O(n^3)$ 정도에 작동한다는 것이다. 정확한 명세는 다음과 같다.

find-$\epsilon$-opt-circ.

  • 입력: $2\epsilon$-optimal circulation $f$, 이를 만족하는 퍼텐셜 $p$
  • 출력: $\epsilon$-optimal circulation $f^\prime$, 이를 만족하는 퍼텐셜 $p^\prime$
  • 수행 시간: $O(n^3)$

이러한 서브루틴이 있다면 Cost Scaling 알고리즘을 바로 유도할 수 있다.

  • $f$ 를 임의의 올바른 circulation 이라고 하자 (Lemma 1을 사용하여 찾음).
  • $\epsilon = C, p = 0$ 으로 초기값을 설정하자.
  • $\epsilon \geq 1/n$ 일 때까지, $(f, p)$ = find-$\epsilon$-opt-circ$(f, p, \epsilon / 2)$ 를 대입하고 $\epsilon$ 을 2로 나눈다.

Observation 16. 위 알고리즘은 $O(n^3 \log (nC))$ 번 이내에 종료한다.

위의 Tardos의 증명을 읽었다면 다음 사실도 관찰할 수 있다.

Lemma 17. 매 $\log (2n)$ 번의 연산마다 새로운 간선이 fix된다. Observation 18. $m \log (2n)$ 번 위 알고리즘을 작동시킬 경우 모든 간선이 fix된다.

고로, 위 알고리즘을 $min(m \log (2n), \log (nC))$ 번 실행시킬 경우 min cost circulation을 찾을 수 있다. 무슨 $C \geq e^m$ 이 아닌 이상 $\log (nC)$ 가 당연히 훨씬 작겠지만, 이론적으로 이 알고리즘이 strongly polynomial이라는 의미가 있다.. 정도로 이해하면 좋을 것이다.

3.1 find-$\epsilon$-opt-circ in Push-relabel paradigm

Push-relabel에는 preflow 라는 개념이 존재해서, $f_{i, j} = -f_{j, i}$ 와 $f_{i, j} \le u_{i, j}$ 조건은 만족하지만 플로우 보존은 성립하지 않는 형태의 플로우를 다룬다. Push-relabel 알고리즘은 이러한 preflow를 push, relabel 연산을 적절히 수행해서 올바른 플로우로 변환한다.

여기서도 비슷한 방식을 사용한다. 먼저 $2\epsilon$-optimal한 circulation이 주어지면, 이 circulation을 $0$-optimal한 preflow 로 바꿔준다. 이는 간단한데, 단순히 $c^p_{i, j} < 0$ 인 모든 간선들에 $f_{i, j} = u_{i, j}$ 를 세팅해서 residual edge가 아니게 해 주는 것이다. 이 preflow가 초기값이고, 우리는 이를 올바른 $\epsilon$-optimal circulation으로 바꾸는 것이 우리의 목표이다.

Push-relabel에서는 excess 가 $0$ 초과인 정점에 대해서 push-relabel을 반복해 준다. 이 과정에서 height function 이라는 함수가 플로우의 방향 등을 설정해주는 역할을 하였다. 여기서도 같은 개념이 정의된다. 먼저 Excess는 기존과 동일하게 $ex_i = \sum_{(k, i) \in E} f_{k, i}$ 이다. height function의 역할을 하는 것은 퍼텐셜 함수 $p$ 이다. 퍼텐셜 함수 $p$ 에 대해서, $c^p_{i, j} < 0$ 일 경우 $i \rightarrow j$ 로 push할 수 있다고 정의한다. 여기서 push와 relabel 연산을 반복해서, 모든 정점의 Excess를 $0$ 으로 만들고 (preflow를 flow로 만들고), 그 과정에서 퍼텐셜 함수가 $\epsilon$-optimal 하게 할 것이다.

구체적으로:

  • push 연산은 $ex_i > 0$ 인 임의의 정점 $i$에 대해서, $c^p_{i, j} < 0$ 인 정점 $j$ 방향으로 플로우를 흘려주는 연산이다. 이 때 흘려주는 양은 $min(u_{i, j} - f_{i, j}, ex_i)$ 이다. $c^p_{i, j} < 0$ 이며 $f_{i, j} < u_{i, j}$ 인 간선 $(i, j)$ 를 admissible 하다고 한다.
  • 만약 $ex_i > 0$ 인 임의의 정점 $i$ 에 대해서 push 연산을 시행해 줄 수 있는 간선이 없다면, 이 정점을 relabel 시켜야 한다. relabel 연산은 $p$ 가 $\epsilon$-optimal한 한도에서 최소한으로 $p_i$ 를 줄여준다. 이는, $f_{i, j} < u_{i, j}$ 가 만족하는 모든 정점에 대해서 $c^p_{i, j} = c_{i, j} + p_i - p_j \ge -\epsilon$ 가 만족하는 최소 $p_i$ 이니, $p_j - c_{i, j} - \epsilon$ 의 최댓값이다. relabel 연산을 한 이후에는 물론 push 연산이 가능하다.

이 과정에서 퍼텐셜 함수는 항상 $\epsilon$-optimal하게 유지됨을 관찰하자 (push 연산에서 생기는 역변은 $c^p_{j, i} > 0$ 을 만족한다).

이것이 find-$\epsilon$-opt-circ 알고리즘 명세의 전부이다. Push-relabel처럼 생각보다 꽤 간단한 알고리즘으로, 자명하지 않은 것은 이 알고리즘이 종료, 그것도 $O(n^3)$ 시간에 종료한다는 것이다. 이것을 증명하기 위한 핵심 Lemma는 다음과 같다.

Lemma 19. 임의의 $i$ 에 대해서, $p_i$ 는 알고리즘 작동 과정에서 최대 $3n\epsilon$ 번 감소한다. Proof. $f$ 를 $p_i$ 가 최종적으로 relabel된 순간의 preflow라고 하고, $f^\prime$, $p^\prime$ 을 초기 $2\epsilon$-optimal circulation 이라고 하자. $p_i$ 가 relabel된 순간에 $ex^f_i > 0$ 이다. $A = {(i, j) f_{i, j} < f^\prime_{i, j}}$ 인 간선 집합에 대해서, $S$ 를 $i$ 에서 $A$ 의 간선을 타고 도달할 수 있는 정점들의 집합이라고 하자. 만약 $S$ 에 있는 모든 정점들에 대해서 $ex^f_k \geq 0$ 이라면,

$- \sum_{k \in S} ex^f_k \= \sum_{k \in S} \sum_{(k, j) \in E} f_{k, j} \= \sum_{k \in S} \sum_{(k, j) \in E, j \notin S} f_{k, j} \\geq \sum_{k \in S} \sum_{(k, j) \in E, j \notin S} f^\prime_{k, j} \\geq 0$.

이고 $i \in S$ 이니 가정에 모순이다. 고로 $ex^f_j < 0$ 인 정점 $j$가 존재하며 $i$ 에서 $j$ 로 가는 경로가 $A$ 상에 있다. 이 경로를 $P = {v_0 = i, v_1, v_2, \ldots, v_{k-1}, v_k = j}$ 라 하면,

  • 모든 간선 $(v_i, v_{i + 1})$ 이 $f$ 의 residual edge이다. $f_{i, j} < f^\prime_{i, j} \le u_{i, j}$ 이기 때문이다.
  • 모든 간선 $(v_{i + 1}, v_i)$ 이 $f^\prime$ 의 residual edge이다. $f^\prime_{j, i} < f_{j, i} \le u_{j, i}$ 이기 때문이다.

이 때

  • $f$ 가 $\epsilon$-optimal 하기 때문에 $-k\epsilon \leq \sum_{(i, j) \in P} c^p_{i, j} = (\sum_{(i, j) \in P} c_{i, j}) + p_i - p_j$
  • $f^\prime$ 이 $2\epsilon$-optimal 하기 때문에 $-2k\epsilon \leq \sum_{(i, j) \in P} c^{p^\prime}{j, i} = (\sum{(i, j) \in P} c_{j, i}) + p^\prime_j - p^\prime_i$

그런데 $ex^f_j < 0$ 이기 때문에 $j$는 relabel이 된 적이 없다. 고로 $p_j = p^\prime_j$ 이다. 모두 연립하면 $-3k\epsilon \le p_i - p^\prime_i$ 가 되고 $k \le n$ 이니 Lemma 19가 성립한다. $\blacksquare$

Lemma 20. Relabel은 최대 $3n^2$ 번 일어난다. Proof. Relabel 연산이 $p_i$ 를 최소 $\epsilon$ 이상 줄인다는 사실을 관찰하자. $\blacksquare$

Lemma 19와 Lemma 20을 결합해서 보았을 때 우리가 왜 $\epsilon$ 을 $0$ 으로 줄일 수도, $1$로 줄일 수도 없고 반으로 나눠야 하는 지를 알 수 있다. 최종 $\epsilon$ 이 작다고 해도 Lemma 19의 statement는 크게 변하지 않으나, 각 relabel이 줄이는 양이 $0$ 내지는 $1$이 되기 때문에 Relabel 과정 자체가 많이 필요하다. 최종 $\epsilon$ 이 크면 서브루틴 호출 자체가 많아지고, 작으면 각 서브루틴의 relabel 횟수가 많아져서, 반으로 했을 때 전자 역시 로그로 유지하면서 relabel의 효과를 최대화 할 수 있다.

이 때문에 실제 구현에서는 $\epsilon / 2$ 가 아니라 다른 수를 쓰는 전략을 사용할 수도 있다. 만약에 실제 상황에서 Relabel 연산이 생각만큼 많이 일어나지 않는다면, 목표 $\epsilon$ 을 줄이는 등의 최적화를 시도할 수 있다는 뜻이다. (예를 들어, $\epsilon / 8$ 정도의 값을 목표로 두면 서브루틴의 호출 수를 3배 줄일 수 있다.)

이후 증명은 전형적인 push-relabel의 틀을 벗어나지 않는다.

Lemma 21. Saturating push는 최대 $6nm$ 번 일어난다. Proof. 간선 $(u, v)$ 에 대해서 한번 saturating push를 한 후 다시 saturating push를 하기 위해서는 역변에 push가 일어나야 하고, 이는 $c^p_{i, j} \geq 0$ 임을 뜻한다. 이 방향으로 push하기 위해서는 $i$ 를 무조건 relabel해야 한다. 고로 2번의 saturating push마다 $i$ 가 한번 relabel되어야 하고, Lemma 19에 의해 이는 한 간선을 최대 $6n$ 번 saturating push할 수 있음을 뜻한다. $\blacksquare$

Lemma 22. admissible edge들은 사이클을 이루지 않는다. Proof. 귀납을 사용한다. 초기에는 admissible edge가 아예 없으니 자명하다. push 연산은 admissible edge를 제거할 수만 있지 새로 만들 수 있어 사이클을 만들 수 없다. relabel 연산은 $i$ 번 정점에서 나가는 새로운 residual edge들을 만든다. 하지만 relabel 연산이 $p_i$ 를 $\epsilon$ 이상 감소시켰기 때문에 $i$ 번 정점으로 들어오는 residual edges들이 다 $c^p_{i, j} \geq 0$ 을 만족하게 된다. 고로 사이클이 생긴다면 $i$ 번 정점을 거쳐야 하는데, $i$ 번 정점을 들어올 수가 없어서 여전히 사이클이 없다. $\blacksquare$

Lemma 23. Non-saturating push는 $O(n^2m)$ 번 일어난다. Proof. $\Phi_i$ 를 $i$ 번 정점에서 admissible edge들을 사용해 도달할 수 있는 정점의 수라고 하고, $\Phi = \sum_{ex_i > 0} \Phi_i$ 라고 하자. 초기에는 모든 정점이 자기 자신만 도달할 수 있으니 $\Phi \le n$ 이다. 최후에는 $ex_i = 0$ 이니 $\Phi = 0$ 이다.

$\Phi$ 가 늘어나는 경우는 두 가지가 있다. 먼저 매 saturating push마다 $ex_i > 0$ 인 정점이 생길 수 있으니 $\Phi$ 가 $n$ 이하로 늘어난다. 또한 relabel 연산 이후 $ex_i > 0$ 인 정점에서 도달할 수 있는 다른 정점들이 생기니 $\Phi_i$ 가 최대 $n$ 늘어난다. 다만 Lemma 22에서 보았듯 다른 정점들이 $i$ 번 정점으로 admissible arc를 통해 도달할 수 없게 되니, 다른 정점들의 $\Phi$ 는 늘지 않는다. 고로 최대 $n(6nm + n^2)$ 만큼 $\Phi$ 가 늘어난다.

$\Phi$는 매 non-saturating push마다 최소 $1$씩 줄어든다: $i$ 가 non-saturating push 이후 $ex_i = 0$ 이 되었기 때문이다. 이 과정에서 다른 정점 $j$ 가 $ex_j > 0$ 이 되었다고 해도, $j$가 도달할 수 있는 정점의 수는 $i$ 가 도달할 수 있는 정점의 수보다 strictly 작다 (일단 부분집합이고, Acyclic하기 때문에, 최소한 $i$는 도달할 수 없기 때문이다). $\blacksquare$

Theorem 24. find-$\epsilon$-opt-circ 알고리즘은 $O(n^2m)$ 시간에 작동한다 (Lemma 20+21+23).

Push-relabel 알고리즘과 동일하게, excess vertices를 FIFO queue로 관리하면 시간 복잡도가 $O(n^3)$ 으로 줄어든다. 플로우 글과 동일하게 이 증명은 생략한다.

4. 알고리즘의 구현

Maximum Flow를 구하는 Push-relabel 알고리즘의 경우 그렇게 구현이 어렵지 않다. 하지만 문제점은 어떠한 휴리스틱을 쓰고 이 휴리스틱들을 어떻게 구현하는지가 성능에 직접적인 영향을 준다는 것이다. 개별 휴리스틱의 구현도 꽤 어려운 편에 속한다. 나의 경우에는 Push-relabel 알고리즘의 구현 자체는 금방 했지만, 다른 구현에 비해서 느리다는 문제 때문에 해당 구현을 폐기하였다 (Dinic과 비슷한 수준의 속도였다).

또한 특정한 휴리스틱의 경우는 기능적인 tradeoff를 요구한다. 예를 들어서, height가 $n$ 초과인 정점들은 $ex_i > 0$ 일지라도 push/relabel하지 않고 영구적으로 지워버리는 휴리스틱이 있다. 이러한 휴리스틱을 사용할 경우 속도 향상이 있지만 답 역추적이 아주 까다롭다. 그래서 Dinic의 경우와는 다르게 구현에 명확한 정답이 없고, 이런 저런 실험적 결과와 본인의 사용 용례를 잘 안배해야지 좋은 구현을 얻을 수 있다.

다행이도 Push-relabel은 인터넷에서 이미 많은 사람들이 구현을 해 놓은 상태라서, 이러한 구현들을 조금 수정하는 식으로 효율적인 Push-relabel 알고리즘을 사용할 수 있었다. 처음에는 Chillee 의 구현을 썼는데, 역추적이 안되는 문제도 있었고, 무엇보다 구현에 버그가 있어서 WA를 몇번 받은 후 사용하지 않았다. 현재는 teapotd 의 구현을 약간 수정한 버전을 사용하고 있다. 이 구현의 경우 역추적이 가능한 형태이고, 여러 문제에서 테스트 했을 때 특별히 버그가 있는 것 같지 않아서 신뢰할 수 있는 구현이라고 생각했다. 본인이 사용하고 있는 코드 라이브러리는 이 곳에서 확인 가능하다.

Min-Cost Circulation을 구하는 Cost scaling 알고리즘의 경우, 일반적인 MCMF 구현보다는 어렵지만 위 글을 이해했다면 충분히 직접 구현할 수 있는 수준이다. Cost scaling의 경우 Push-relabel에서 사용하는 여러 휴리스틱이 적용 불가능하기 때문에, 오히려 휴리스틱에 대한 걱정을 좀 줄일 수 있다. 내가 구현한 Cost Scaling 코드는 이 곳에서 확인 가능하다. 휴리스틱을 전혀 사용하지 않아도 충분히 빠르게 작동했고, 간단한 휴리스틱 몇 개를 넣으니 성능을 더 향상시킬 수 있었다. 구현하면서 염두에 뒀던 점은

  • $\epsilon$ 을 줄일 때 반으로 줄이지 않고 $1/8$ 로 줄였다 (속도 면에서 가장 효율적이었다).
  • $\epsilon$ 을 실수로 관리할 경우 실수 연산이 동반되어 느리고 부정확하다. 모든 Cost를 $n+1$ 배하게 되면, Observation 11의 threshold가 $n+1$ 배 되어 $\epsilon(f) \le 1$일 경우 Optimal circulation을 얻을 수 있다. 이렇게 할 경우 정수 연산만으로 문제를 해결할 수 있다.

Efficient implementations of minimum-cost flow algorithms 글을 보면 Cost scaling에 적용할 수 있는 여러 최적화 기법들이 정리되어 있다. 빠른 구현체들을 보았을 때 몇몇 구현은 push-look-ahead 휴리스틱을 사용하는 것 같았다. 조금 복잡해 보여 나는 따로 배우지 않았는데, 관심 있다면 한번 시도해 볼 만한 것 같다. 사실 나의 최종 Cost Scaling 구현에는 두 가지 정도의 휴리스틱들이 있는데, 논문에 있는 내용과는 별로 상관이 없는 휴리스틱이고 maroonrk 의 코드를 참고했다. 아주 간단한 휴리스틱들인데 특정 상황에서 정말 비약적인 속도 향상이 있어서 놀랐다. 휴리스틱을 사용한 나의 코드는 위 두 저지에서 가장 빠른 Cost scaling 코드 중 하나고, BOJ의 할일 정하기 2를 0.25초에 해결할 수 있다. 

5. 참고 자료