Thorup-Zwick Oracle

간선에 음이 아닌 가중치가 있는 무방향 그래프 $G$가 주어졌을 때, 다음과 같은 쿼리를 처리하자:

• 1 u v: $u, v$ 간의 최단 경로의 길이를 반환한다.

..는 어려운 문제이다. Balanced separator를 쉽게 찾을 수 있거나 하는 특수 케이스가 아니면 보통 $O(nm)$ 시간에 Dijkstra를 $n$ 번 돌리는 방법보다 좋은 방법이 없다. 그러니까 다음과 같은 Approximate 버전을 생각하자. 초기에 정수 파라미터 $k \geq 1$ 이 같이 주어졌을 때:

• 1 u v: $u, v$ 간의 최단 경로의 길이가 $d$ 라면, $[d, (2k-1)d]$ 범위에 있는 수를 출력하라.

실제 출력한 수를 길이로 가지는 경로가 존재하지 않을 수도 있지만, 일단 오늘 얘기할 알고리즘에서는 항상 있는 경로의 길이만 반환하며, 동일한 길이의 경로를 역추적도 할 수 있다. 알고리즘 성질상 자명하니 걱정하지 않아도 된다.

이 문제는 Thorup-Zwick Oracle이라고 불리는 대단히 유명한 풀이가 존재한다. 짧은 논문인데 이상하게 아무리 읽어도 이해가 안 되어서 접어두고 있었는데, 그냥 힌트로만 생각하고 직접 유도하는 식으로 접근하니 이해가 되었다. 그래서 그 과정을 설명한다.

1. Warmup: $O(m \sqrt n \log n)$, $k = 2$

편의상 모든 정점의 차수가 $O(1)$ 이라고 가정하자. 고로 $m = O(n)$ 이다. 이 가정은 나중에 자연스럽게 없어진다.

$\sqrt n$ 개의 정점을 아무렇게나 고르고 이를 $S$ 라고 하자. $S$ 에 있는 모든 정점들에 대해서 Dijkstra를 돌리자. 이러면 쿼리 정점 중 하나가 $S$ 에 있는 경우는 정확한 거리를 쉽게 알 수 있다.

문제는 쿼리 정점이 모두 $S$ 밖에 있는 경우이다. 구체적으로, 쿼리 $u, v$ 에 대해서 $u$ 와 $v$ 는 가까운데 $S$ 가 $u, v$ 에서 굉장히 멀리 있다고 하면, $S$ 에서 시작한 Dijkstra가 아예 도움이 안 되고 $3$배 안에서 틀릴 수 있다는 조건도 의미가 없다.

$D(S, u)$ 를 $S$ 에 있는 임의의 정점에서 $u$ 까지의 최단 경로라고 하자. 즉, $D(S, u) = \min_{v \in S} dist(v, u)$ 이다. 만약 $D(S, u) \le dist(u, v)$ 가 만족한다고 하자. $s_{min} \in S$ 를, $S$ 에서 $u$ 에 가장 가까운 정점 (즉, $D(S, u) = dist(s_{min}, u)$) 이라고 할 때, $dist(s_{min}, u) + dist(s_{min}, v)$ 를 그냥 출력하면 이는 최단 경로의 3배 안에 있다. 왜냐면

$dist(s_{min}, u) \le dist(u, v)$
$dist(s_{min}, v) \le dist(s_{min}, u) + dist(u, v) \le 2 dist(u, v)$

즉 $S$ 가 $u, v$ 의 거리에 대비해서 멀지 않으면 실제로 문제는 이미 해결되었다. 고로 어려운 경우는 $dist(u, v) < D(S, u)$ 인 경우 뿐이다. $Close(u) = \{v \mid dist(u, v) < D(S, u)\}$ 라고 하자. $Close(u)$ 를 모든 정점에 대해서 계산할 수 있다면, 다음과 같이 문제를 해결할 수 있다:

• $v \in Close(u)$ 인지 본다
  • 맞으면 계산한 거리를 반환
  • 아니면 $s_{min}$ 을 계산하고 $dist(s_{min}, u) + dist(s_{min}, v)$ 를 출력 ($s_{min}$ 계산은 전처리 가능)

$Close(u)$를 계산하려면 $n$ 번의 Dijkstra가 필요하지 않냐고 물을 수 있고 실제로 그렇다. 하지만 Dijkstra를 잘 생각해 보면 거리가 증가하는 순서대로 탐색을 한다. 고로 $D(S, u)$ 를 알고 있으면 (실제로 알고 있고) 거리가 $D(S, u)$ 이상이 되는 시점에 커팅을 해주는 식으로 최적화를 할 수 있다. 이 경우 시간 복잡도는 $Close(u)$ 에 속하는 모든 정점의 차수 합, 곱하기 $O(\log n)$ 이 될 것이다. $S$ 를 랜덤하게 고르면 (즉, 각 정점을 $1/\sqrt n$ 의 확률로 고르면) $Close(u)$ 의 크기가 대충 $O(\sqrt n)$ 정도다.

• Lemma 1.1. 모든 정점 $u$ 에 대해서, $Close(u)$ 의 크기의 기댓값은 $O(\sqrt n)$ 이다.
• Proof. $u$ 에서 거리가 멀어지는 순서대로 모든 $n-1$ 개의 정점을 정렬하자. 순서상 $i$ 번째 정점이 $Close(u)$ 에 속하려면, $1, \ldots, i$ 번 정점이 모두 $S$ 에 속하지 않아야 한다. $S$ 는 이 정렬 순서와 독립적으로 선택되니, 이 확률은 $(1 - 1/\sqrt n)^i$ 이다. 이를 모두 합하면 $O(\sqrt n)$ 이 된다.

모든 정점의 차수가 $O(1)$ 이라고 앞에서 가정했으니, $Close(u)$ 는 모두 $O(n \sqrt n \log n)$ 시간에 계산할 수 있다. 각 쿼리는 해시셋을 사용하여 $O(1)$ 시간에 대답할 수 있다.

2. 모든 $k$ 에 대해 작동하는 랜덤 풀이

이제 위 풀이를 모든 $k$ 에 대해 작동하게끔 일반화하자. $k \in [1, O(\log n)]$ 을 가정한다 (더 큰 $k$를 잡는 의미가 없다.)

초기화 알고리즘은 다음과 같다:

• 정점 집합 $A_0, A_1, \ldots, A_k$ 를 다음과 같이 설정:
  • $A_0 = V$
  • $A_1$ 은 $A_0$ 에서 각 원소를 $n^{-1/k}$ 의 확률로 독립 샘플
  • $A_2$ 는 $A_1$ 에서 각 원소를 $n^{-1/k}$ 의 확률로 독립 샘플
  • ...
  • $A_{k-1}$ 은 $A_{k-2}$ 에서 각 원소를 $n^{-1/k}$ 의 확률로 독립 샘플
  • $A_k$ 는 무조건 공집합.
• 각 $v \in V$ 에 대해서
  • $p_i(v)$ 를, $D(A_i, v) = dist(p_i(v), v)$ 를 만족하는 $p_i \in A_i$ 로 설정
  • $Close_i(v)$ 를, $\{w \mid w \in A_i \setminus A_{i+1}, dist(w, v) < D(A_{i+1}, v)\}$ 로 설정
  • $Close(v) = \cup_i Close_i(v)$
  • $Close(v)$ 에 있는 모든 원소 $w$ 에 대해서, $dist(w, v)$ 는 모두 알고 있음

초기화 알고리즘은 대략 $O(k m n^{1/k})$ 시간 정도에 동작하게끔 구현할 수 있다. 일단 여기에 대해서는 나중에 생각하고, 이런 초기화 알고리즘이 있을 때 어떻게 각 쿼리를 해결하는지 알아보자. $(u, v)$ 가 쿼리로 주어졌을 때:

• 피벗 $w$ 를 잡는다. 초기에는 $v$ 로 두자. 자명히, $w \in A_0$ 이며, $dist(w, v) = 0$ 이다.
• $w \in Close_0(u)$ 인지를 확인한다. 맞으면 $dist(u, v)$ 를 반환하고 종료한다.
• 아니면 피벗을 $w = p_1(u)$ 로 설정한다. 고로 $w \in A_1$ 이다. 또한 $dist(w, u)$ 를 안다.
• $w \in Close_1(v)$ 인지를 확인한다.
  • $dist(w, u)$ 를 아니까, 맞으면 $dist(w, u) + dist(w, v)$ 를 반환하고 종료한다.
  • 아니면 피벗을 $w = p_2(v)$ 로 설정한다. 고로 $w \in A_2$ 이며 $dist(w, v)$ 를 안다.
• 여기서부터는 반복한다.
  • 즉, 불변량은 $w \in A_{2i+1}$ 이고 $dist(w, u)$ 를 알거나 $w \in A_{2i+2}$ 이고 $dist(w, v)$ 를 아는 두 상황 중 하나이다.
  • 구현에서는 $Close_i(v)$ 인지를 확인할 필요 없고 그냥 $Close(v)$ 를 전부 봐도 된다.

$A_k$ 가 무조건 공집합이 되게 설정해놨으니 어느 순간 알고리즘은 무조건 종료하게 되어 있다. 따라서 알고리즘이 $O(k)$ 에 작동하는 것도 자명하다.

그렇다면 알고리즘은 왜 $(2k-1)d$ 이하의 거리를 반환할까? 이 알고리즘의 중요한 불변량은, $w \in A_p$ 일 때 $dist(w, u)$ 혹은 $dist(w, v)$ 를 알고 있다는 사실이다. 이 때 알고 있는 거리의 값이 $pd$ 이하임을 귀납법으로 보일 수 있다.

• $p = 0$ 일때는 자명하다.
• $w \in A_{p-1}$ 이며 $dist(w, u) \le (p-1)d$ 임을 알고 있다고 하자 (WLOG $p$는 짝수). $dist(w, v) \le dist(w, u) + dist(u, v) \le pd$ 이다. $w \notin Close_{p-1}(v)$ 이니, $dist(p_d(v), v) \le dist(w, v) \le pd$ 가 된다.

알고리즘은 $w \in Close_p(v)$ 가 성립할 때 종료하게 되며, 위에서 설명했듯이 이러한 $p < k$ 가 존재한다. 이 상황에서 아는 거리는 $pd$ 이하일 것이고, 모르는 거리 역시 삼각부등식에 의해 $(p+1)d$ 이하일 것이다. 고로 반환되는 거리는 $(2p+1)d \le (2k-1)d$ 이하임이 보장된다.

나는 이런 식으로 생각하니까 조금 더 시각적으로 와닿았던 것 같다. $u - v$ 를 잇는 최단 경로를 수직선 위에 그리자. 첫 스텝에서, $Close_0(u)$ 에 $v$ 가 있는지 찾아본다. 없다면 레벨 $1$ 에 $dist(u, v) \le dist(u, w)$ 인 $w$ 를 찾을 수 있다. 이제 $Close_1(v)$ 에 레벨 $1$ 정점 $w$ 가 있는지 찾아본다. 없다면 레벨 $2$ 에 $dist(v, w') \le dist(v, w)$ 인 $w'$ 을 찾을 수 있다. 이 과정은 $k-1$ 번 안에 무조건 끝나고, $w$ 가 최악으로 행동하는 것은 $u - v$ 를 잇는 최단 경로에서 $u, v, u, v$ 를 기준으로 계속 점대칭되어서 이동하는 경우 뿐이다. 삼각부등식에 의해 이 행동을 아무리 해도 최단 경로에서 $(k-1)$ 배 이상 멀어질 수 없다.

3. $O(kmn^{1/k})$ 시간에 구현하기

Dijkstra 한번을 $O(m + n)$ 시간에 돌릴 수 있음을 가정한다. 이는 입력 간선의 가중치가 $[0, poly(n)]$ 범위의 정수이면 참이다. 아닐 경우에는 $\log n$ 이 붙는다.

초기화 알고리즘에서:

• 샘플링 부분은 $O(kn)$ 시간에 구현할 수 있음이 자명하다.
• $p_i(v)$ 를 구하는 것은 흔히 Multi-source Dijkstra라고 하는, 초기에 $A_i$ 에 속하는 정점을 모두 $0$으로 초기화한 후 Dijkstra를 돌리는 방식으로 $O(km)$ 시간에 구현할 수 있다.
• $p_i(v)$ 를 구하는 과정에서 $D(A_i, *)$ 역시 모두 계산된다.

고로 여기까지는 쉽다.

$Close_i(v) = \{w \mid w \in A_i \setminus A_{i+1}, dist(w, v) < D(A_{i+1}, v)\}$ 만 빨리 구할 수 있으면 된다. Warmup에서는 $v$ 를 고정하고 모든 $w$ 를 구했지만, 여기서는 $w$ 를 고정하고 $w \in Close_i(v)$ 인 모든 $v$ 를 찾을 것이다. $v$ 를 고정했을 때는 $Close_i(v)$ 를 구하는 방법을 쉽게 이해할 수 있다. $D(A_i, v)$ 도 같이 고정되어서 이 threshold를 넘지 않는 선에서 갱신을 하면 정확히 $Close_i(v)$ 만 구하기 때문이다. 하지만 $w$ 를 고정할 경우 threshold가 계속 변하기 때문에 모든 정점을 방문해야 하지 않나 걱정될 수 있다.

다행히도 걱정할 필요가 없다. 왜냐면:

• Lemma 3.1. $w \in Close_i(v)$ 라면, $w \rightarrow v$ 를 잇는 최단 경로 상에 있는 모든 정점 $p$ 에 대해 $w \in Close_i(p)$.
• Proof: 최단 경로 상에 있는 모든 $p$ 에 대해 $dist(w, p) + dist(p, v) = dist(w, v)$ 이다. 한편 $D(A_{i+1}, p) + dist(p, v) \ge D(A_{i+1}, v)$ 이다. ($A_{i+1}$ 에 있는 모든 정점으로 $0$ 의 가중치로 갈 수 있는 dummy source가 있다는 식으로 생각하면 쉽다.) 고로 $dist(w, p) + dist(p, v) = dist(w, v) < D(A_{i+1}, v) \le D(A_{i+1}, p) + dist(p, v)$ 이고 따라서 $dist(w, p) < D(A_{i+1}, p)$ 가 성립한다.

고로 $dist(w, v) < D(A_{i+1}, v)$ 인 경우에만 heap에 넣는 식으로 Dijkstra를 구현하면 $Close_i(v)$ 를 정확하게 구할 수 있다. $Close(v)$ 의 크기가 작다는 사실은 앞과 똑같은 방식으로 보일 수 있다.

• Lemma 3.2. $E[|Close(v)|] \le k n^{1/k}$.
• Proof. $E[|Close_i(v)|] \le n^{1/k}$ 임을 보이면 충분하다. Warmup과 동일하게 증명할 수 있다. $A_i$ 에 있는 정점들을 거리 순으로 정렬하자. 순서상 $j$ 번째 정점이 $Close_i(v)$ 에 속하려면 $1, 2, \ldots, j$ 번 정점이 모두 $A_{i+1}$ 에 속하지 않아야 한다. $A_{i+1}$ 은 이 정렬 순서와 독립적으로 선택되니, 이 확률은 $(1 - n^{-1/k})^j$ 이다. 이를 모두 합하면 $O(n^{1/k})$ 이 된다.

이에 따라서 모든 Dijkstra의 수행 시간 합은 $\sum deg(v) \cdot k n^{1/k} = O(kmn^{1/k})$ 가 된다. Warmup에서 degree가 상수라는 가정이 도움이 된 것은, $Close(v)$ 에 속하는 정점의 차수 합을 알 수 없어서였다. 하지만 $w$ 를 기준으로 Dijkstra를 돌리면 각 정점을 방문하는 횟수가 $Close_i(v)$ 의 크기와 일치하기 때문에 수행 시간 합이 쉽게 증명된다.

4. Hitting Set을 사용하여 랜덤 없애기

사실 쿼리 알고리즘은 $V = A_0 \supseteq A_1 \supseteq A_2 \supseteq \ldots \supseteq A_k = \emptyset$ 을 만족하는 아무 $A_i$ 에 대해서 성립한다. 그러니까 위 알고리즘에서 랜덤성이 필요한 부분은 Lemma 3.2에서 크기를 bound하는 부분 말고는 전혀 없다.

이 사실을 사용해서 알고리즘을 derandomize하자. $A_i$ 가 고정되어 있을 때 이를 토대로 $A_{i+1}$ 을 고를 것이다. 랜덤 알고리즘과 정확히 동일한 성능을 내려면, 고르는 $A_{i+1}$ 은 다음 성질을 만족해야 한다:

• 모든 정점 $v$ 에 대해서, $A_i$ 의 정점들을 거리 순으로 정렬했을 때, 앞 $O(n^{1/k})$ 개 원소 중 $A_{i+1}$ 에 속하는 원소가 있거나, $|A_i| \le O(n^{1/k})$ 여야 한다.
• $A_k = \emptyset$
• $|A_{i+1}| \le |A_i| \cdot n^{-1/k}$

세 번째 조건은 필수가 아니고 첫 두 조건만 있으면 되지만, 세 번째 조건을 안 쓰고 첫 두 조건을 만족시키는 것을 상상하기 어렵다.

모든 정점 $v$ 에 대해서, $S_v \subseteq A_i$ 를, $A_i$ 에 있는 정점들 중 $v$ 에서 가장 가까운 $O(n^{1/k})$ 개를 고른 집합이라고 정의하자. 이러한 $S_v$ 는, Dijkstra를 변형해서 (구체적으로 multi-source를 돌리는데 각 정점에 대해 방문 횟수가 $O(n^{1/k})$ 이상이면 커팅하는 식으로) $O(m n^{1/k} \log n)$ 시간에 계산할 수 있다.

우리가 고르는 $A_{i+1}$ 은 크기가 충분히 작아야 하며 또한 모든 $v$ 에 대해 $S_v \cap A_{i+1} \neq \emptyset$ 이어야 한다. $S_v$ 들이 모두 주어졌을 때 $A_{i+1}$ 을 구하는 방법이 있을까? 더 나아가서 $A_{i+1}$ 의 크기를 최소화 할 수 있을까? 이 문제를 Hitting Set이라고 한다:

Hitting Set. $\{1, 2, \ldots, u\}$ 의 부분집합 $S_1, S_2, \ldots, S_n$ 이 주어졌을 때, $S_i \cap H \neq \emptyset$ 을 만족하는 최소 크기 집합 $H$ 를 구하여라.

$|S_i| = 2$ 라는 조건을 추가하면, Hitting Set은 Vertex Cover와 동일한 문제이다. 즉 이 문제는 효율적으로 해결할 수는 없다. 하지만 다음과 같은 그리디 근사 알고리즘이 존재한다:

Greedy Algorithm for Hitting Set. 알고리즘은 초기에 빈 집합 $H = \emptyset$ 에서 시작하고, 매번 $H$ 에 새로운 원소를 추가하는 식으로 작동한다. 또한, $S_i \cap H \neq \emptyset$ 인 $S_i$ 는 그때그때 제거해 준다. $x \in \{1, 2, \ldots, u\}$ 중, 현재 남은 $S_i$ 에 가장 많이 포함되는 (즉 $S_i$ 를 최대로 제거할 수 있는) $x$ 를 골라서 $H$ 에 삽입하고, $x \in S_i$ 인 $S_i$ 를 모두 제거한다.
Analysis. 모든 $S_i$ 의 크기가 충분히 크다면, 예를 들어 파라미터 $s$ 이상이라면, 이 알고리즘은 충분히 좋은 $S$ 를 고른다. 현재 남은 집합의 크기가 $n'$ 개라면, 단순한 카운팅 논리에 의해 최적의 $x$ 는 $\frac{s n'}{u}$ 개 이상의 집합을 제거할 것이다. $n(1 - s/u)^{u / s (\ln n + 1)} < 1$ 이라, $|H| \le u/s(\ln n + 1)$ 이다.
Implementation. $S_i$ 의 첫 $s$ 개가 아닌 원소는 그냥 무시하자. 각 $u$ 개의 원소에 대해서 해당 집합에 속하는 $S_i$ 의 개수를 구하고 최댓값을 관리하면 ($O(1)$ 시간에 작동하는 적당한 heap 자료구조 사용) 전체 문제를 $O(u + sn)$ 시간에 해결할 수 있다.

이 그리디 알고리즘을 우리의 문제 상황에 적용하면, $u = O(n^{1-i/k}), s = O(n^{1/k})$ 이기 때문에 $|A_{i+1}| \le O(n^{1 - (i+1)/k} \log n)$ 이라는 bound를 얻게 된다. $\log n$ 이 붙는 것이 다소 귀찮은데, 깔끔하게 해결하는 것은 첫 조건을 다음과 같이 바꾸는 것이다:

• 모든 정점 $v$ 에 대해서, $A_i$ 의 정점들을 거리 순으로 정렬했을 때, 앞 $O(n^{1/k} \log n)$ 개 원소 중 $A_{i+1}$ 에 속하는 원소가 있거나, $|A_i| \le O(n^{1/k} \log n)$ 여야 한다.

(3)의 증명을 읽어 보면 $O(\log n)$ 을 붙여도 정당성에는 차이가 없음을 알 수 있다. 이제 $|A_{i+1}| \le O(n^{1-(i+1)/k})$ 가 성립하여, 원하는 $A_i$ 를 구할 수 있다.

그리디 알고리즘의 수행 시간은 $S_v$ 를 얼마나 빠르게 구하느냐에 따라 결정되는데, 위에서 말했듯이 $S_v$ 의 계산은 $O(m n^{1/k} \log^2 n)$ 시간에 가능하다 (첫 설명과 다르게, $A_i$ 의 크기가 $\log n$ 만큼 커져 $\log n$ 이 붙는다). 고로 전체 문제도 $O(k mn^{1/k} \log^2 n)$ 시간에 해결할 수 있다.

5. 간선 삽입 쿼리?

이하 내용은 https://arxiv.org/abs/2005.02368 논문에서 발췌했다.

(2)에서 이야기한 쿼리 알고리즘을 다시 한번 살펴보자. 임의의 정점 $u, v$ 가 주어졌을 때, 쿼리 알고리즘이 반환하는 답의 형태는 항상 $dist(w, u) + dist(w, v)$ 의 형태이다. 이 때 $dist(w, v)$ 는 $dist(p_i(v), v)$ 의 형태이거나 $w \in Close_i(v)$ 의 형태이다. 고로, $u, v$ 간의 최단 경로를 계산하기 위해서 필요한 정보는 각 $i \in [k]$ 에 대한 $dist(p_i(v), v)$ 값, 그리고 $Close(v)$ 집합에 대한 정보가 전부이다. 이 집합의 크기는 각 정점마다 총 $O(k n^{1/k} \log n)$ 밖에 되지 않는다 (랜덤을 사용하지 않았을때)

이를 사용해서 amortized $\tilde{O}(n^{1/k} \sqrt m)$ 시간에 다음 두 쿼리를 지원하는 자료구조를 구성할 수 있다:

• 간선 추가
• 두 정점 $s, t$ 에 대해 $(2k-1)$-approximate 최단 경로 계산

방법은 간단하다. 다음과 같이 하면 된다:

• 자료구조 초기화: Thorup-Zwick Oracle을 구성한다. 또한 처리한 쿼리가 $\Theta(\sqrt m)$ 개가 될 때마다 자료구조를 처음부터 다시 초기화한다. (Oracle을 $\tilde{O}(mn^{1/k})$ 시간에 구성할 수 있으니 괜찮음.) 추가로, 빈 그래프 $H$ 를 만든다.
• 간선 $(u, v)$ 추가: $H$ 에 가중치 $w(u, v)$ 의 간선 $(u, v)$ 을 추가해 주고, $dist(p_i(u), u), dist(p_i(v), v), Close(u), Close(v)$ 를 $H$ 에 추가해 준다.
• $(s, t)$ 쿼리: $H$ 에 $dist(p_i(s), s), dist(p_i(t), t), Close(s), Close(t)$ 를 추가해준다. 처리한 쿼리가 최대 $O(\sqrt m)$ 개이니 $H$ 에 있는 간선은 최대 $\tilde{O}(n^{1/k} \sqrt m)$ 개이다. $H$ 에 있는 정보로 $dist(s, t)$ 를 충분히 계산할 수 있다. 고로 다익스트라로 최단 경로를 계산해주면 된다.

이 경우에는 작은 그래프 $H$ 를 한 레벨로만 쌓아서 $O(\sqrt m)$ 의 수행 시간이 나왔지만, 여러 레이어로 더 쌓으면 approximation factor를 악화시키는 대신 수행 시간을 줄일 수 있다. 예를 들어, $10$ 레벨을 쌓으면 다음과 같이 자료구조가 구성된다. 가장 낮은 레벨 (즉 사용자에게 가장 가까운 레벨) 이 $1$ 레벨이다.

• $i (1 \le i \le 10)$ 레벨 자료구조 초기화: Thorup-Zwick Oracle을 구성한다. 또한 처리한 쿼리가 $\Theta(m^{1-i/10})$ 개가 될 때마다 자료구조를 처음부터 다시 초기화한다. (Oracle을 $\tilde{O}(mn^{1/k})$ 시간에 구성할 수 있으니 괜찮음.) 추가로, $i+1$ 레벨 자료구조 $H$ 를 만든다.
• 간선 $(u, v)$ 추가: $H$ 에 가중치 $w(u, v)$ 의 간선 $(u, v)$ 을 추가해 주고, $dist(p_i(u), u), dist(p_i(v), v), Close(u), Close(v)$ 를 $H$ 에 추가해 준다.
• $(s, t)$ 쿼리: $H$ 에 $dist(p_i(s), s), dist(p_i(t), t), Close(s), Close(t)$ 를 추가해준다. 처리한 쿼리가 최대 $(m^{1-i/10})$ 개이니 $H$ 에 있는 간선은 최대 $\tilde{O}(n^{1/k} m^{1-i/10})$ 개이다. $H$ 에 있는 정보로 $dist(s, t)$ 를 충분히 계산할 수 있다. 고로 $H$ 에 똑같이 $(s, t)$ 쿼리를 해서 최단 경로를 계산해 주면 된다.

이 경우 각 레벨에서 에러가 $(2k-1)$ 배씩 곱해져서, $(2k-1)^{10}$ - approximate 최단 경로를 계산하게 된다. $i$ 번 레벨에 간선을 $T$ 개 추가하면 $i+1$ 번 레벨에 간선을 $\tilde{O}(T n^{1/k})$ 개 추가하게 된다. 고로 한 업데이트는 최종 레벨에 $\tilde{O}(n^{10/k})$ 개 정도 추가하게 될 것이다. 계산해 보면 $O(m^{1/10} n^{10/k})$ 정도의 update time을 얻게 된다.

원 논문에 따르면, $l$ 개의 레벨을 쌓았을 때 다음과 같은 결과가 나온다고 한다.

• Approximation factor $(2k-1)^l$
• 업데이트 및 쿼리 $O(l \cdot O(k)^l \cdot m^{1/(l+1)} \cdot n^{l/k} \cdot \log^{l-1} n)$

사실 내 생각에는 $O(\log^{2l-1} n)$ 인것 같지만 뭐 대충 그런 걸로 하자. 위와 같이 여러 레이어로 자료 구조를 쌓을 경우, (4) 에 있는 derandomization이 도움이 된다. 랜덤을 썼을 때 크게 문제가 되는 건 아니지만, deterministic할 경우 다음 레벨에 넣게 되는 간선 개수가 단순 기댓값이 아니라 항상 worst-case로 보장이 되기 때문이다.