Node Ranking of Trees

이 글은 GPT 4.5가 최종 편집하였다. 썸네일 역시 GPT로 생성했지만, 본문의 내용과는 아무 관련이 없다.

그래프의 Vertex Ranking은 다음 조건을 만족하는 labeling $\rho : V \to \mathbb{Z}_{\ge 1}$로 정의된다.

서로 다른 두 정점 $u, v$에 대해서 $\rho(u) = \rho(v)$라면, 이들을 연결하는 모든 경로상에 항상 $\rho(x) > \rho(u)$를 만족하는 정점 $x$가 존재해야 한다.

이때 $\rho(v)$의 최댓값을 vertex ranking number 또는 vertex ranking chromatic number $\chi_{vr}(G)$라고 부른다. 당연히 일반적인 chromatic number보다는 크거나 같다. 트리에 대해서는 비교적 간단한 알고리즘이 알려져 있지만, 일반 그래프에서는 Hitting Set Problem과 관련 있다는 사실만 알려져 있다. 이 글에서는 트리의 vertex ranking을 구하는 $O(n)$ 알고리즘을 소개한다.

이 문제는 BOJ 1868번 문제를 통해 직접 채점할 수 있다. 문제의 설명을 통해 vertex ranking이 트리의 search query complexity와 관련된다는 점을 확인할 수 있다.

우선 Centroid Decomposition이 항상 유효한 vertex ranking을 제공하므로, 항상 $\chi_{vr}(T) \le \log_{1.5} n$이 성립한다. 이 점을 염두에 두고 최적의 ranking을 유도해보자. 편의상 $\rho(v)$를 "$v$의 rank"라고 부르자. 트리 DP를 이용해서 각 정점 $v$의 서브트리들에서 같은 rank를 가진 정점들이 연결되지 않도록 $\rho(v)$를 정해주고자 한다. (Base case는 정점이 하나뿐인 경우이며, 이때는 $\rho(v)=1$로 설정하면 된다.)

귀납적으로 $v$의 각 서브트리는 이미 올바르게 ranking되었다고 가정하자. 여기서 중요한 정점들은 서브트리 내에서 "local max"가 되는 정점들이다. 즉, 루트 $v$까지 올라오는 경로에 자기보다 높은 rank의 조상이 없는 정점들을 의미한다. 정의상 이런 정점들은 rank마다 최대 하나씩 존재할 수 있으므로, 서브트리마다 local max는 최대 $O(\log n)$개 존재한다.

다음의 간단한 관찰을 할 수 있다:

• 어떤 rank $r$이 두 개 이상의 서브트리에서 등장하면, 반드시 $\rho(v) > r$이어야 한다. 그렇지 않으면 두 local max가 연결되기 때문이다.
• 또한 $\rho(v)$는 서브트리의 local max들 중에 없는 값이어야 한다.

이 두 가지 관찰을 이용해 $\rho(v)$를 다음과 같이 그리디하게 결정하자.

• 서브트리의 모든 local max 중에서 등장하지 않으면서, 자기보다 큰 값이 최대 한 번만 등장하는 최소의 값 $q$.

놀랍게도, 이 방식이 최적의 ranking을 준다. 서브트리의 기존 labeling을 수정할 필요도 없다. 이렇게 $\rho(v)$를 정한 뒤에는 local max들 중에서 값이 $q$보다 큰 정점들만 유지하여 위로 전달하면 된다.

위 알고리즘을 그대로 구현하면 $O(n \log n)$에 동작하고, 조금 더 효율적인 자료구조를 활용하면 $O(n)$에도 동작한다. (이 글에 유사한 아이디어가 잘 정리되어 있다.) 각 정점에서 서브트리들을 합칠 때 rank는 최대 1씩 증가하므로, 두 번씩 등장하는 최댓값을 찾는 과정을 최대가 아닌 서브트리의 rank 합만큼의 시간 내에 처리하면 $O(n)$을 증명할 수 있다.

이제 우리가 위에서 그리디하게 정한 labeling $\rho$가 최적임을 증명하자.

일단 유효한 $\rho$라면, rank가 최대인 정점은 정확히 하나만 존재할 수 있다. 두 개 이상 존재한다면, 그 정점들은 반드시 자기보다 낮은 rank의 정점들로만 연결되기 때문에 모순이다.

이제 $\chi_{vr}(T)$에 대한 귀납법을 사용하자. Base case로 $\chi_{vr}(T)=1$인 경우는 자명히 정점이 하나뿐이며 우리의 그리디한 방식으로 정한 $\rho$가 최적이다.

$\chi_{vr}(T) > 1$인 경우, 앞서 언급했듯이 우리가 정한 $\rho$에 대해 rank가 최대인 정점 $w$의 서브트리 $T_w$를 제거하자. 귀납 가정에 따라, 트리 $T - T_w$는 우리가 제안한 그리디 방식으로 항상 최적의 ranking이 결정된다. 이 값은 반드시 $\chi_{vr}(T - T_w) \le \chi_{vr}(T)$를 만족하므로, 서브트리 $T_w$의 존재 여부는 다른 정점들의 rank 결정 과정에 전혀 영향을 주지 않는다.

$\rho(w)=\chi_{vr}(T)$였다는 것은 $\rho(w)$ 미만의 값들이 반복해서 등장한다는 의미다. 두 번 이상 등장하는 가장 큰 값을 $p$라 하자. (그런 값이 없다면 $p=0$이라 하면 된다.) 그러면 rank 구간 $[p+1, \rho(w)-1]$의 각 값이 local max로 정확히 한 번씩 등장한다.

이제 rank 구간 $[p, \rho(w)-1]$ 각각의 local max를 포함하는 서브트리를 생각해 보자. 이들은 서로소거나 포함 관계로 이루어진 laminar set 구조를 가진다. 만약 포함 관계를 이루는 두 서브트리 $T \subseteq T'$가 있다면 $T' - T$를 고려하여 서로소로 만들 수 있다.

귀납 가정에 따라, 이렇게 얻은 각 서로소 서브트리를 labeling하려면 반드시 대응되는 local max 값만큼의 label이 필요하다. (서로소로 만들기 전) 서브트리들이 서로 포함하는 경우에는 약간 더 엄밀하게 따져 줘야 하지만, $T_w$가 위 서브트리에 영향을 주지 않는 이유와 비슷하다. 따라서 임의의 다른 ranking $\rho'$을 사용하더라도, 이 서브트리들은 rank 구간 $[p+1, \rho(w)-1]$의 local max를 각각 한 번씩 만들어야 하고, ($p > 0$이라면) rank $p$인 local max를 두 번 만들어야 한다. 그러므로 당연히 $\rho'(w) \ge \rho(w)$이어야 한다. 증명 끝.