Graph Spanners

Undirected graph $G = (V, E)$ 에 대해, $G$의 $t$-spanner $H = Spanner(G,t) = (V, E^\prime)$ 는 다음 성질을 만족한다:

• $E^\prime \subseteq E$
• 모든 $u, v \in V$ 에 대해, $dist(H, u, v) \le dist(G, u, v) \times t$
• $E^\prime$ 의 크기가 작음

즉, 최단 경로를 Approximate하게 보존하는 Sparsification이다. Equivalent하게, 다음과 같이 표현할 수도 있다.

• $E^\prime \subseteq E$
• 모든 $(u, v) \in E$ 에 대해, $dist(H, u, v) \le dist(G, u, v) \times t$
• $E^\prime$ 의 크기가 작음

일단 이 글에서는 Unweighted case만 다룬다.

---

Existence and Naive Algorithm

Theorem 1. $n$ 개의 정점을 가진 그래프에 대해, $O(n^{1+1/k})$ 개의 간선을 가진 $(2k-1)$-spanner 가 존재하며, 다항 시간에 찾을 수 있다.

Theorem 1을 증명하기 위해, 그러한 spanner를 찾는 다항 시간 알고리즘을 제안한다 (Alt93) 초기 $H$ 를 빈 그래프로 설정하고, $G$ 의 간선들을 순서대로 (어떤 순서여도 상관 없음) 보면서 다음과 같이 처리한다.

현재 처리하는 간선이 $e = (u,v)$ 일 때:

• $dist(H \cup {e}, u, v) \le 2k-1$ 일 경우 무시.
• $dist(H \cup {e}, u, v) > 2k-1$ 일 경우 $H$ 에 간선을 추가.

이 알고리즘이 다항 시간임은 자명하다.

이 알고리즘이 $(2k-1)$-spanner 를 찾는 것을 증명하자. Equivalent한 정의를 사용하면 자명하다. 만약 $H$ 가 $(2k-1)$-spanner가 아니라면, $G$ 의 간선 중 $dist(H, u, v) > 2k-1$ 인 간선이 존재하는데, 이 간선을 처리했을 때 거리가 $(2k-1)$ 이하일 수가 없기 때문에, 가정에 모순. (이 파트의 증명에서는 $2k-1$ 인 것이 중요하지 않다. 그냥 $k$ 로 바꿔도 전혀 상관없고, $2k-1$ 인 것은 간선 개수 부분에서 사용된다.)

마지막으로 이 알고리즘이 최대 $O(n^{1+1/k})$ 개의 간선을 가짐을 증명한다.

Lemma 2. 위 알고리즘으로 만든 그래프에는 길이 $2k$ 이하의 사이클이 없다.
Proof. 사이클이 있다고 하면, 마지막으로 추가된 간선이 조건에 의해 무시되어야 한다.

만약에 위 알고리즘으로 만든 그래프가 $c n^{1+1/k}$ 개 초과의 간선을 사용한다고 하자. 차수가 $2c n^{1/k}$ 이하인 간선들을 반복적으로 지우다 보면, 모든 정점의 차수가 $2cn^{1/k}$ 초과인 비지 않은 그래프를 얻을 수 있다. 아무 정점을 잡고 거리 $k-1$ 이하의 정점들을 모두 탐색하자. 거리 $k-1$ 이하의 정점들로 induce된 그래프는 사이클을 만들지 않는다. 고로 깊이 $k-1$ 이하인 정점들의 개수가 최소 $O(n^{(k-1)/k})$ 개이고, 이들의 neighbor가 겹치지 않으므로 그래프의 정점 개수가 $n$ 개 초과가 된다. 고로 가정에 모순이다.

Theorem 1에 의해서, 모든 그래프는 $O(n^{1+1/k})$ 개의 간선을 가진 $(2k-1)$-spanner를 가진다. 다시 말해, $O(n \sqrt n)$ 개의 간선을 가진 $3$-spanner가 있고, $O(n^{4/3})$ 개의 간선을 가진 $5$-spanner가 있고, $O(n)$ 개의 간선을 가진 $O(\log n)$-spanner가 있다. 즉, $k = \omega(\log n)$ 의 경우는 그다지 흥미롭지 않다 (위와 같은 spanner를 얻는 방법을 모르는게 아니면).

임의의 $k$ 에 대해서, 이보다 잘 하는 것은 불가능하다고 추측되고 있다 (Erdos' Girth Conjecture).

---

Exponential Clock Algorithm (MPX13)

Spanner를 얻는 가장 좋은 방법은 Exponential Clock Algorithm 라고 생각한다. 이 알고리즘은 기존의 효율적인 Spanner Algorithm (Baswana's algorithm 등) 과 Low-diameter decomposition algorithm 을 모두 일반화하고 단순화하였다는 점에서 가지는 가치가 크다. (Recall: Low diameter decomposition은, 그래프에서 $\delta m$ 개의 간선을 지워서 남은 connected component의 diameter를 $O(\delta \log n)$ 으로 만들 수 있다는 정리이다. Low diameter decomposition은 항상 존재하고, 알고리즘의 역할은 지울 간선의 집합을 찾는 것이다.)

편의상 $k = \log n$ 이라고 가정하고 Spanner를 찾자. 더미 노드를 만들고, 더미 노드에서 각 정점으로 가중치 있는 간선을 잇는다. 이 때 각 간선의 가중치는:

• $n/2$ 개의 정점을 랜덤하게 고른 후 해당 정점에 가중치 $1$
• 남은 정점 중 $n/4$ 개의 정점을 랜덤하게 고른 후 해당 정점에 가중치 $2$
• 남은 정점 중 $n/8$ 개의 정점을 랜덤하게 고른 후 해당 정점에 가중치 $3$
• 남은 정점 중 $n/16$ 개의 정점을 랜덤하게 고른 후 해당 정점에 가중치 $4$
• $\ldots$

그리고 해당 더미 노드에서 시작해서 Dijkstra를 돌린다. (초기 distance가 있는 그래프에서 multi-source dijkstra를 돌린다고 생각해도 된다.) 위 간선의 가중치가 아주 작으니, Dijkstra algorithm을 BFS로 대체해도 됨을 쉽게 관찰할 수 있다. 시간 복잡도도 $O(m)$ 이다.

BFS로 최단 경로를 모두 구해두면, 최단 경로 트리를 얻을 수 있다. 이 트리의 루트는 더미 노드이고, 더미 노드의 트리 상 자식들은 (서브트리 안에 있는 것 말고 직계 자식) 모두 원래 그래프의 정점일 것이다. 더미 노드의 각 자식이 이루는 서브트리를 클러스터 라고 하자. 다음 사실이 성립한다.

Lemma 3a. 모든 간선 $e$ 에 대해 $e$ 의 양 끝점이 서로 다른 클러스터에 속할 확률은 $1/2$ 이하이다.

이 사실에서 바로 Spanner와 Low-diameter decomposition algorithm을 모두 얻을 수 있다:

• Low-diameter decomposition: 위 클러스터링이 그냥 $\delta = \frac{1}{2}$ 에서의 Low-diameter decomposition이다. 높은 확률로 더미 노드에서 모든 정점까지의 거리가 최대 $O(\log n)$ 이기 때문이다.
• Spanner construction: 위 과정을 독립적인 랜덤 변수에서 $O(\log n)$ 번 돌리고, 클러스터 내부의 BFS 트리를 모두 Spanner에 넣자. Lemma에 의해 높은 확률로 이 시행 중 한번은 양 끝점이 같은 끝점에 속한다. 그 시행에서 BFS 트리를 타는 경로를 사용하면 거리가 $O(\log n)$ 이 된다. 고로 총 $O(n \log n)$ 개의 간선을 가지는 $O(\log n)$-spanner를 찾을 수 있다.

위 과정에서 랜덤하게 가중치를 부여한 방법을 복잡한 어휘로 짧게 얘기하면, 각 정점의 초기 거리를 평균이 $2$ 인 exponential distribution 에서 샘플링하였다고 할 수 있다. 평균을 $2$ 가 아니라 $\frac{1}{\delta}$ 로 바꾸면, Lemma statement가 다음과 같이 바뀐다:

Lemma 3b. 임의의 $\delta \le 1/2$ 에 대해 모든 간선 $e$ 에 대해 $e$ 의 양 끝점이 서로 다른 클러스터에 속할 확률은 $\delta$ 이하이다.
Corollary 3b. 임의의 $\delta \le 1/2$ 에 대해 Low diameter decomposition을 $O(m)$ 시간에 찾을 수 있다.

Lemma 3b (3a) 의 증명은 MPX13의 Corollary 4.5에서 찾을 수 있다.

---

Exponential Clock Algorithm for Spanners (MPVX15)

Exponential Clock Algorithm을 통해 Spanner를 아주 간단하고 효율적인 방법으로 얻을 수 있지만, 아직 몇 가지 한계점이 있다.

• $k = \log n$ 인 경우만 해결했다.
• 간선 개수가 $\log n$ 배 증가한다.
• 계산량이 $\log n$ 배 증가한다.

약간의 변경을 추가하면 위 세 문제를 모두 해결할 수 있다. 평균이 $\frac{2k}{\log n}$ 인 exponential distribution에서 거리를 샘플링하고 클러스터를 구하자. 클러스터 내부의 BFS 트리를 전부 Spanner에 넣고, 모든 정점 $v$ 에 대해서, 해당 정점과 인접한 클러스터 $c$ (정점 $v$ 와 클러스터 $c$ 가 인접하다는 것은 $v$ 와 인접한 정점 $w \in c$ 가 존재한다는 것이다.) 와의 간선을 각 클러스터마다 하나씩 Spanner에 넣는다. 즉, $v$ 에 인접한 서로 다른 클러스터의 개수가 $c(v)$ 라면 $c(v)$ 개의 간선을 Spanner에 추가하는 것이다.

이 과정을 $O(\log n)$ 번 반복할 필요는 없고, 그냥 딱 한 번 돌리면 된다. 고로 시간 복잡도는 hash map을 사용하면 $O(m)$ 이다.

이 알고리즘이 올바른 Spanner를 구하는 것은, 높은 확률로 더미 노드에서 모든 정점까지의 거리가 $O(k)$ 라는 점에서 따라온다. 어떠한 간선이 같은 클러스터를 이으면, 스패닝 트리를 타면 되기 때문에 거리가 $O(k)$ 이다. 어떠한 간선이 다른 클러스터를 잇고 삭제되었다고 하자. 끝점을 공유하며, 같은 클러스터를 잇고, 삭제되지 않은 간선이 존재한다. 이 간선을 사용한 후, 스패닝 트리를 타면 된다. 고로 알고리즘의 반환 결과는 올바른 $O(k)$-spanner가 된다.

알고리즘의 간선 개수는 다음 Lemma에 의해 따라온다 (MPVX15의 Corollary 3.1).

Lemma 3c. 모든 정점에 대해 $c(v)$ 의 기댓값은 $O(n^{1/k})$ 이다.

---

Exercise. 위 알고리즘을 사용하여 Decremental Spanner를 $O(\text{poly log}(n))$ amortized update에 관리하는 알고리즘을 고안하여라. 알고리즘이 관리하는 spanner는 최대 $O(n^{1+1/k})$ 개의 간선을 가지며 stretch가 $O(k)$ 이다. (Hint 1, Hint 2)

Exercise. 위 알고리즘을 사용하여 Fully-Dynamic Spanner를 $O(\text{poly log}(n))$ amortized update에 관리하는 알고리즘을 고안하여라. 알고리즘이 관리하는 spanner는 최대 $O(n^{1+1/k} \log n)$ 개의 간선을 가지며 stretch가 $O(k)$ 이다. (Hint)