Dynamic $(\Delta+1)$-coloring

최대 차수가 $\Delta$ 인 그래프를 $(\Delta + 1)$ 개의 색으로 색칠하는 문제를 생각해 보자. 이 문제는 정점을 아무 순서로 보면서 남는 색을 배정해 주면 선형 시간에 쉽게 해결할 수 있다. 그러니 간선이 추가되고 삭제되는 쿼리를 넣어보자. 쿼리당 $O(\Delta)$ 시간에 문제를 해결하는 것은 쉽다:

• 간선이 삭제되면 아무것도 하지 않는다.
• 간선이 추가되었고, 만약 두 정점의 색이 다르다면, 한 정점에 대해서 남는 색을 배정해 준다. 남는 색을 찾아줘야 하기 때문에 $O(\Delta)$ 시간이 필요하다.

더 빠른 알고리즘은 없을까? 이 문제를 처음 다룬 것은 내가 알기로는 Bhattacharya et al. 2018 이고, 당시에는 expected amortized $O(\log \Delta)$ 시간이 필요했다. 자료구조 자체도 다소 복잡한 편에 속한다. 현재는 expected worst-case $O(1)$ 시간에 하는 방법 (Ghaffari, Koo 2025) 이 존재한다. 이 알고리즘은 저번 학기 지도교수님과 내가 함께 작업한 알고리즘이다. 쉬운 작업은 아니었지만, 결론적인 알고리즘은 매우 간단하다. PS 좀 한 사람 아무나 잡고 10분 안에 설명할 수 있을 거 같다.

각 정점에 다음과 같은 방식으로 랜덤하게 라벨을 배정한다:

• 절반의 정점을 랜덤하게 잡은 후 라벨 $0$ 을 배정한다.
• 그리고 남은 정점 중 절반을 랜덤하게 잡은 후 라벨 $1$ 로 배정한다.
• 그리고 남은 정점 중 절반을 랜덤하게 잡은 후 라벨 $2$ 로 배정한다.
• ...

모든 정점 $v$ 에 대해서, 인접한 노드 중 라벨이 $k$ 이상인 노드의 수 기댓값은 최대 $\Delta \cdot 2^{-k}$ 임을 볼 수 있다.

각 정점 $v$ 에 대해서, 해당 정점과 인접하면서 레벨이 해당 정점 이하인 색의 리스트를 관리한다. $nb_{\leq}(v)$ 를 $v$ 보다 레벨이 작거나 같은 $v$ 의 이웃의 수라고 하면, 리스트의 크기는 $nb_\leq(v)$ 이하이다. 즉, 리스트에 등장하지 않는 색의 개수는 최소 $\Delta + 1 - nb_\leq(v)$ 개이다.

간선 삭제시에는 아무것도 할 필요가 없다. 간선이 추가되었는데 두 정점의 색이 다르다면 이것도 아무것도 할 필요가 없다. 그러니까 간선이 추가되었는데 두 정점의 색이 같은 경우가 문제다. 두 정점 중 가장 최근에 색이 바뀐 정점을 잡고 이 정점에 대해서 새 색을 부여한다. 이 과정을 Recolor라고 부르자.

Recolor는 어떻게 할까? 이 리스트에서 등장하지 않는 색을 랜덤하게 샘플링하자. 등장하지 않는 색을 샘플링해야 하는데, 해시 테이블 장난질을 하면 $O(1)$ 에 가능하다. 샘플링한 후 다음과 같은 작업을 하자:

• 해당 색을 가진 이웃의 개수가 몇 개인지를 Naive하게 세어 준다.
• 해당 색을 가진 이웃이 $0$ 개면 그냥 그 색을 먹으면 된다.
• 해당 색을 가진 이웃이 $1$ 개면, 그 이웃의 색을 먹고, 그 이웃을 재귀적으로 Recolor한다.
  • 이 이웃의 레벨은 나보다 무조건 높다.
• 해당 색을 가진 이웃이 $2$ 개 이상일 확률은 $1/2$ 이하이다. 그래서 그 경우에는 다시 샘플링한다.
  • $1/2$ 초과일 경우 $\frac{1}{2}(\Delta + 1 - nb_\leq(v)) \times 2$ 개 초과의 이웃이 나보다 레벨이 크다. 그래서 차수가 $\Delta$ 보다 커진다.

$v$ 의 라벨을 $l(v)$ 라고 하자. $v$를 Recolor하는 횟수 기댓값이 $O(1)$ 이다. 거기에 naive하게 이웃을 도는 것까지 생각해 보면 한 정점을 Recolor하는데 드는 시간은 $O(\Delta \cdot 2^{-l(v)})$ 이다. $1$ 개일 때 움직이는 이웃은 나보다 레벨이 높기 때문에 이후의 연산량 기댓값은 현재의 $1/2$ 이다. 고로 조화급수에 따라서 알고리즘 전체에서 써야 할 시간 기댓값은 $O(\Delta \cdot 2^{-l(v)})$ 이다.

근데 생각해 보면 각 색이 샘플링될 확률이 최대 $1/(\Delta \cdot 2^{-l(v)})$ 이다. 왜냐면 샘플링 가능한 색의 개수가 $v$ 보다 레벨이 큰 이웃의 수보다 크기 때문이다. 이 확률이, $v$ 에 인접한 간선을 추가했을 때 반대쪽 끝점과 색이 똑같을 확률보다 크거나 같다. 그래서 애초에 Recolor가 불릴 확률이 최대 $1/(\Delta \cdot 2^{-l(v)})$ 이다. 곱하면 기댓값이 $O(1)$ 이 된다.

위에서 설명한 알고리즘을 그대로 구현하면 갱신 시간 기댓값이 amortized $O(1)$ 이다. 심심할때 일부 정점을 랜덤하게 재색칠하면 amortized를 뗄 수 있다. 결론을 내는 과정에서 대부분의 확률 변수를 독립 변수라고 가정했기 때문에, 엄밀한 증명은 아니다. 엄밀한 증명이 당연히 안 궁금하겠지만, 혹시 궁금하면 원문을 읽어보면 된다.