Poly-space TSP algorithms, directed planar graph separations, Baswana's algorithm

잠자고 있던 퀄리티 낮은 scribe 몇개를 기록용으로 올린다.

Hamiltonian Path in $O(2^nn^c)$ time, $O(n^c)$ space

Karp의 1982년 논문이라고 들었다.

존재 여부 대신 경우의 수 mod p를 세자. random p를 잡아서 decision problem으로 바꿀 수 있다.

길이 n의 (simple) path를 세는 대신 길이 n의 walk를 세는 건 쉬움. 그냥 sumA^{n-1}(i, j). 그런데 길이 n의 walk가 모든 정점을 방문하면 그게 hamilton path이다. 그래서 모든 정점 부분 집합에 대해서 포배하면 끝.

TSP in $O(4^n n^c)$ time, $O(n^c)$ space

모든 $i, j$ 에 대해 $i$ 에서 출발해서 모든 정점을 다 돌고 $j$ 에 돌아오는 TSP의 최단 경로를 기록하자.

현재 정점 집합 크기가 $n$ 개일 때, 모든 크기 $n/2$ 의 부분집합을 다 해보자. 이후, 각 부분집합이 찾은 최단 경로 행렬을 다항 시간에 합쳐준다. 뭐 $A[i][j] = min(A[i][j], L[i][k] + w(k, l) + R[l][j])$ 같은 느낌으로.

이러면 시간 복잡도는 $T(n) = 2^n \times T(n/2) + n^c$ 의 꼴로 나온다. ($2\binom{n}{n/2} \leq 2^n$) $T(n) = n^c + 2^n(n/2)^c + 2^n 2^{n/2} (n/4)^c + \ldots = 4^n poly(n)$. 공간 복잡도는 자명히 다항

Separation in planar graphs

undirected planar graph는 sqrt(n) 크기의 balanced separator가 있다는 사실이 잘 알려져 있다 (link) 이걸 토대로 sqrt(n) overhead에 이런 저런 자료구조들을 많이 만들 수 있음. distance oracle도 할 수 있고, directed reachability oracle 등등..

directed reachability는 근데 더 잘할 수가 있다 (Thorup'04). 증명 없이 간단하게만 소개한다.

Defn. Directed graph가 주어졌을 때, 2-layered spanning tree를 다음과 같이 정의한다.

• spanning tree (in a undirected sense)
• root-node path는 최대 2개의 directed path의 concatenation으로 표현될 수 있음

Claim (abridged). Directed planar graph가 주어졌을 때, 이를 다음과 같은 조건을 만족하는 k개의 directed planar graph로 선형 시간에 분할할 수 있다:

• 각 directed planar graph의 정점과 간선 개수 합은 O(n+m)
• 각 directed planar graph에 대해서 2-layered spanning tree가 존재함

Claim에 따라서 Directed planar graph가 항상 2-layered spanning tree를 가진다고 가정할 수 있다. 사실 위에 적어둔 것으로는 그게 명확하지 않은데 구체적인 clarification은 원문을 확인하면 좋을듯.

Lemma. Directed planar graph와 2-layered spanning tree가 주어졌을 때, balanced separator인 fundamental cycle C가 존재한다.
Lemma. C의 안과 밖에 있는 그래프를 In, Out이라고 하자. C를 contract했을 때, 원래 그래프의 2-layered spanning tree는 In + C, Out + C에서도 여전히 2-layered spanning tree이다.

C는 balanced separator인데, 2-layered spanning tree의 fundamental cycle이기도 함. 그래서 C는 4개의 directed path로 partition할 수 있음

Corollary. Directed planar graph는 (사실상) 4개의 vertex disjoint directed path로 이루어진 balanced separator가 존재한다.

Lemma. Directed graph G와 그 위의 directed path P에 대해서, P의 정점을 거치는 u - v path가 있는지를 선형 시간 전처리와 O(1) 쿼리에 알 수 있다.
Proof. SCC 만들고 DP.

고로 near-linear time에 directed planar reachability를 $O(\log n)$ 에 해결할 수 있다.

여담으로, undirected planar graph에서 separator를 찾는 방법을 잘 보면, triangulation을 해준 후 어떤 cycle을 잡는 식으로 작동함을 알 수 있다. 그러니까 triangulated undirected planar graph는 cycle (=path) 형태의 balanced separator가 존재한다. triangulation이 없어도 3개의 vertex disjoint path로 이루어진 balanced separator가 존재한다고 알고 있음.

Baswana's Algorithm

Unweighted graph에서 $(2k-1)$-spanner를 계산하는 알고리즘은 Halperin & Zwick 에 의해 처음 발견되었다 (HZ96). 다만 Publish되지는 않았는데, 링크 건 글에 잘 설명되어 있는듯. 이 글에서는 Baswana's Algorithm (BS07) 이라는 다른 알고리즘을 소개한다.

아이디어는 그래프의 노드들을 가지고 일종의 Cluster tree를 구성하는 것인데, 정확히 tree는 아니고, 약간 리프에서부터 Bottom-up 으로 올라가는 느낌이다.

모든 $0 \le i \le k$ 에 대해서 level $i$ 를 정의하자. level $i$ 에서는 다음과 같은 정보들을 저장한다:

• Subgraph $G_i = (V_i, E_i)$ ($V_i \subseteq V, E_i \subseteq E$)
• $V_i$ 의 partition $C_i$ ($C_i$ 를 $V_i$ 의 Clustering이라고 부르고, $C_i$ 를 이루는 각 집합을 Cluster라 부른다.)
• 각 Cluster $C_{i, j}$ 를 span하는 rooted tree (루트가 고정되어 있다.)
• Spanner에 들어가는 간선 집합 $H_i$

Level $0$ 에서는

• $G_0 = G$
• $C_0$ 은 모두 singleton set (모든 정점이 자기만으로 이루어진 Cluster에 속함)
• singleton set이니 rooted tree의 루트는 자기 자신이고, 간선은 없음
• $H_0 = \emptyset$

이제 Level $i-1$ 의 내용이 계산되었다고 했을 때 이를 토대로 Level $i$ 의 내용을 계산하자. 알고리즘은 $C_{i-1}$ 을 이루는 클러스터들을 $n^{-1/k}$ 의 확률로 random sample한다. sampling에서 선택된 클러스터들은 트리와 함께 그대로 Level $i$ 의 내용에 들어간다. 고로 선택되지 않은 클러스터에 속하는 정점들이 문제가 된다. (아래에서 "클러스터" 라고 하면 그 기준은 $C_{i-1}$ 의 클러스터링이다. $C_i$ 의 클러스터링은 여기서 만드는 거지 참고되는 것은 아니다.)

어떠한 정점 $v$ 가 선택되지 않은 클러스터에 속한다고 하자. 만약 이 정점과 인접한 다른 정점 $w$ ($(v, w) \in E_{i-1}$) 가 선택된 클러스터에 속한다면, $v$ 를 그 클러스터에 넣고 $(v, w)$ 를 대응되는 rooted tree의 간선으로 추가한다. 여러 개가 있다면 그 중 아무거나에 들어가면 되는데, 어떠한 consistent한 random order $\sigma$ 가 있어서, 그 order가 작은 것을 우선하여 들어간다고 하자. (여기서는 상관이 없고 쿼리가 추가되면 약간 중요해진다.)

만약 모든 인접한 다른 정점이 클러스터에 선택되지 않았다고 하자. 확률을 생각해 보면, $C_{i-1}$ 기준으로, 이 정점이 인접한 서로 다른 클러스터의 개수는 대략 $n^{1/k}$ 개 이하일 것이다. 만약 $v$ 에서 같은 클러스터로 가는 간선이 두 개 이상 있다면, 그 중 단 하나만 남긴다. 이렇게 되면 이 정점의 차수는 $n^{1/k}$ 이하가 된다. $H_i$ 에 이 정점과 인접한 모든 간선을 추가한다.

마지막으로 $G_i = (V_i, E_i)$ 에서, $V_i$ 는 $C_i$ 에 들어간 모든 정점으로 설정하고, $C_i$ 를 span하는 rooted tree의 모든 간선을 $H_i$ 에 넣는다. Level $k$을 계산할 때는 선택된 클러스터를 $0$ 개로 고정시켜버린 후 똑같이 하면 된다. $\cup_{i \in [k]} H_i$ 가 원하는 Spanner가 된다.

이 알고리즘은 $\tilde{O}(km) = \tilde{O}(m)$ 시간에 작동한다. 이제 $\cup_{i \in [k]} H_i$ 가 올바른 $(2k-1)$-spanner임을 증명한다. (랜덤 관련 논증은 패스)

• 크기: 알고리즘은 모든 정점을 지우고, 각 정점을 지울 때 $n^{1/k}$ 개의 간선을 추가한다. 고로 Spanner는 최대 $O(n^{1+1/k})$ 개의 간선을 가진다.
• 정당성: Level $i$ 에서 rooted tree의 깊이는 최대 $i$ 이다. 고로 임의의 두 정점 간 거리는 항상 $2i$ 이하로 보존된다. 간선을 지울 때, (남긴 하나의 간선) + ($i-1$ 클러스터의 트리 상 경로) 는 Spanner에 존재하며, 그 거리도 $2i-1$ 이하이다.

Fully Dynamic Variant of Baswana's Algorithm

Baswana's Algorithm을 간선 추가/제거 쿼리에도 작동할 수 있도록 응용해 보자. 문제의 구조에 대한 세 가지 관찰이 필요하다.

첫 번째 관찰은 제거 쿼리만 처리할 수 있으면 Bentley-Saxe를 적용할 수 있다는 것이다. 이는 문제가 기본적으로 Decomposable한 성질을 가지고 있기에 가능하다.

Lemma 3. $E_1 \cup E_2 \cup \ldots E_t = E$ 일 때, $H_i$ 가 $(V, E_i)$ 에 대한 $k$-Spanner라면, $\cup H_i$ 는 $(V, E)$ 에 대한 $k$-Spanner이다.
Proof. 어떠한 간선 $(u, v) \in E_j$ 에 대해 $\cup H_i$ 에서의 거리가 $k$ 초과였다면, $H_j$ 에서의 거리도 $k$ 초과일 것이고, 그렇다면 이 간선은 $H_j$ 에 들어가야 했을 것이다.

Lemma 4. $\tilde{O}(m)$ 초기화 시간, $\tilde{O}(1)$ 쿼리 시간에 Decremental Spanner 문제를 해결할 수 있으면, $\tilde{O}(m)$ 초기화 시간, $\tilde{O}(1)$ 쿼리 시간에 Fully Dynamic Spanner 문제를 해결할 수 있다.
Proof. Bentley-Saxe를 그대로 적용하는데, $l_0 = \lceil \log_2 (n^{1+1/k}) \rceil$ 이라고 했을 때, invariant를 $|E_i| \le 2^{i + l_0}$ 로 잡자. 이렇게 되면 각 간선이 매 초기화에 $\tilde{O}(1)$ 만큼 기여하고, 그러한 초기화를 최대 $O(\log n)$ 번 참여한다.

첫 번째 관찰에 따라서 Decremental Query만 고려한다.

두 번째 관찰은, 위 알고리즘에서 그래프의 간선이 어떻게 되든, 클러스터의 중심은 변하지 않는다는 것이다. Level $0$ 에서는 모든 정점이 중심이고, Level $1$ 에서는 그 중 $n^{(k-1)/k}$ 개를 샘플링했다. 이 샘플링은 간선 구조와는 완전히 무관하다. Level $2$ 에서도 그 중 $n^{(k-2)/k}$ 개를 샘플링할 것이며 이 역시 간선 구조와 무관하다. 이 논리가 반복된다. 고로, Decremental Query를 적용할 때 클러스터의 중심 집합은 변하지 않는다고 생각해도 좋다.

세 번째 관찰은, 중심을 안다고 하면 $C_i$ 를 알기 위해서 굳이 $C_{i-1}$ 을 알 필요는 없다는 것이다. 현재 알고리즘의 정의에서 $C_i$ 는 $C_{i-1}$ 에 따라 귀납적으로 정의되지만, 사실은 그냥 선택된 중심에서의 거리가 $i$ 이하인 정점을 모으는 과정이기 때문이다. 만약 각 클러스터의 중심, 그리고 $(V_i, E_i)$ 를 안다면, $C_i$ 는 샘플링된 클러스터의 중심을 큐에 모두 넣고 BFS를 해서 알 수 있다. 정확히는, 큐에 샘플링된 클러스터의 중심을 넣었을 때 (multi-source BFS. 중심은 위에서 얘기한 random order $\sigma$ 를 기준으로 추가), 각 정점에 가장 먼저 도달한 중심이 해당 정점이 속하는 클러스터이다. 만약 거리가 $i$ 초과면 탐색하지 않는다. 이 관점에서, 앞에서 얘기한 "인접한 정점이 클러스터에 선택된 경우" "그렇지 않은 경우" 는, $C_i$ 의 중심과의 거리가 정확히 $i$ 인지, $i$ 초과인지를 가르는 것과 똑같다.

사실 세 번째 관찰의 주장은 아주 정확한 주장은 아니다. 어떠한 정점이 선택된 클러스터 중심과의 거리가 $i$ 이하이지만, 선택되지 않은 클러스터의 중심에 훨씬 더 가깝다면 이 정점은 원래 알고리즘에서는 무시되는 정점이다. 하지만 세 번째 관찰에 의해, 우리의 새 알고리즘은 $C_i$ 에 이 정점을 포함시킨다. 원래 알고리즘의 증명을 살펴보면 $C_i$ 의 크기가 커진다고 손해를 보는 부분이 없고, 고로 이러한 변주를 하여도 상관이 없다.

또한, $C_{i-1}$ 은 알 필요가 없지만 $V_{i-1}$ 은 알 필요가 있다. $V_{i-1}$ 이 달라질 경우 $C_{i-1}$ 에 확실히 영향을 끼치는 것은 명확한게, $V_{i-1}$ 에 없는 정점을 shortcut으로 사용해서 범위를 넓힐 수가 있기 때문이다.

모든 관찰을 종합해 보면

• $C_i$ 를 구성하기 위해서는 $V_{i-1}$ 만 알면 된다.
• $C_i$ 에서 거리 $i$ 초과인 정점들은 $C_{i-1}$ 의 구성만 알면 된다.

거리 $i$ 초과인 정점들은 이후 레이어에 영향을 끼치지 않으니, $C_{i-1}$ 의 구성에 종속적인 개체들이라고 생각할 수 있다. 고로 유일하게 중요한 dependency는 정점의 부분집합이다.

이제 간선 $(u, v)$ 를 그래프에서 지우고 어떠한 일이 일어나는지 살펴보자. 각 정점에 대해 가능한 변화는 다음과 같다:

• 아무 일도 없다. (아무 것도 안 해주면 됨)
• 어떠한 정점이 $C_i$ 상의 다른 클러스터로 이동한다.
• 어떠한 정점이 클러스터에서 완전히 탈락한다.

Even-Shiloach Algorithm을 사용하여 BFS 트리를 관리하고, 위와 같은 변화를 전부 기록해 주자. 다만 우리가 관리하는 BFS 트리가 몇 가지 불변량이 있기 때문에 다소 세심할 필요가 있다.

• 먼저, 하나의 BFS 트리만 관리할 것이다. Multi-source BFS는 결국 더미 노드를 루트로 만들어주는 것으로 해석할 수 있다. 그 트리만 관리할 것이다.
• 모든 부모 중 클러스터의 lexicographic order를 최소화하는 부모를 골라야 한다. 이를 관리하는 데 있어서 Even-Shiloach가 관리하는 invariant가 도움이 되는데, 그래도 조금 더 노력이 필요하다. 각 노드에 대해서 거리 뿐만 아니라 클러스터 번호까지 지정해주고, order를 볼 때 이 클러스터 번호를 기준으로 정렬해 주자. 거리가 달라지지 않는 기준 현재 부모 뒤만 보면 되는 커팅은 그대로 사용할 수 있다. 거리가 달라질 경우 클러스터 번호를 다시 매겨줘야 하는데, 그냥 다시 정렬해줘도 무방하다. $O(\log n)$ 정도가 더 붙을 수는 있겠다.
• Even-Shiloach Algorithm은 모든 노드에 대해서 부모 변화를 전부 기록하고 반환한다. 부모가 바뀌는 과정에서 클러스터 번호가 바뀌었다면, 자식에 대해서도 이를 모두 전파시켜줘야 한다. 이 부분을 Naive하게 탐색하는 식으로 구현하면 실제 ES의 바운드가 깨진다. 클러스터가 이동하는 노드들의 개수 bound는 아직 없고, 그 노드들에 대해서도 $deg(v)$ 의 연산이 필요하기 때문이다. 다만 이후에 클러스터 이동 연산이 실제로 $\tilde{O}(1) \times deg(v)$ 의 연산을 요구함을 보일 거고, 그래도 괜찮음을 증명할 것이기 때문에, 그 부분의 증명에 의존하면 문제가 생기지 않는다.

BFS 트리의 깊이가 $i$ 이면 Even-Shiloach Algorithm을 사용하여 BFS 트리를 쿼리당 amortized $O(i)$ 에 관리할 수 있다.

클러스터를 이동하는 경우에는 $V_i$ 가 그대로 보존되니, $i+1$ 번 레이어에서 탈락된 정점들을 관리할 때에만 (거리 $i+1$ 초과) 차이점이 생긴다. 탈락한 정점들이 관리해야 하는 정보는, 모든 인접한 컴포넌트들에 대해서 컴포넌트와 자신을 잇는 간선 하나이다. 이 간선들은 BST를 사용하여 bookkeeping해 줄 수 있다. 해당 정점에 인접한 정점들에 대해서 위와 같은 자료구조를 적당히 관리해 주자.

클러스터에서 완전히 탈락하는 경우에는 세 가지 일이 일어난다. 첫 번째로 이 정점이 $V_i$ 에서 지워지고, 두 번째로 위에서 관리한 bookkeeping 정보들을 수정해 줘야 하며, 세 번째로 이 정점에 인접한 모든 클러스터에 대한 간선들을 spanner에 추가해야 한다. $V_i$ 에서 지우는 것은 결국 인접한 간선들을 전부 $i+1, i+2, \ldots$ 레벨의 decremental BFS tree에서 지우는 것이 되기 때문에 직접 해 주면 된다. (어차피 추가할 일은 없다). Bookkeeping 정보들은 앞 케이스와 똑같이 하면 된다. 세 번째는 그냥 인접한 정점들을 다 돌면서 나이브하게 처리해 줘도 된다. (bookkeeping 정보들을 참고해도 되겠다.)

두 경우 모두, $\tilde{O}(1) \times deg(v)$ 정도의 시간에 관리를 할 수 있다. 한 정점의 상태가 특별히 엄청 많이 바뀔 수 있다면 비효율적일 수 있지만, 모든 정점에 대해 바뀌는 횟수가 충분히 작다면 amortize되어서 상관이 없다. 이 문제의 경우 모든 정점에 대해서 바뀌는 횟수가 충분히 작다.

Lemma 5. Level $i$ 에 있는 모든 정점은 최대 $O(i \log n)$ 번만 상태를 바꾼다.
Proof. 각 정점의 루트로의 거리는 감소하지 않으니, 루트로의 거리가 "그대로 유지" 되는 경우를 $O(\log n)$ 으로 bound시키면 위 사실을 보일 수 있다. 정점과 가장 가까운 클러스터의 중심과의 거리를 $d$ 라고 하였을 때, 거리가 $d$ 인 클러스터 중심들의 집합을 ${c_1, c_2, \ldots, c_k}$ 라고 하자. 간선이 제거되면서 이 클러스터 중심들의 집합은 서서히 줄어들 것이다. 고로 각 중심들을 현재 간선 제거 시퀀스에서 제거되는 순서대로 정렬하자 ($c_1$ 이 가장 먼저 제거되고, $c_2$ 가 그 다음....). 어떠한 $c_i$ 가 해당 정점과 가장 가까운 클러스터의 중심이 되려면, $c_i$ 는 $c_i, c_{i+1}, \ldots, c_k$ 중에서 $\sigma$ 기준 등장이 가장 빨라야 한다. ($c$ 는 adversarial할 수 있지만) $\sigma$ 는 random하니, 이 확률은 $\frac{1}{k-i+1}$ 이다. 합하면 $O(\log n)$ 이 된다.

어떠한 정점에서 가장 가까운 center가 된다는 것은 결국 이 정점을 기준으로 한 random permutation 기준 이 center가 최소라는 것과 동일하다. random permutation에서 random하게 숫자들을 지웠을 때, 최솟값이 바뀌는 기댓값은 $O(\log n)$ 이다. 고로 상태를 바꾸는 횟수가 충분히 적다.