Dynamic Maximal Independent Set

그래프의 최대 독립 집합 문제는, 그래프가 주어졌을 때 최대 크기의 정점 부분집합 $S$를 골라서, $S$ 안에 있는 두 정점을 잇는 간선이 없게끔 하는 문제이다. 이 문제는 NP-complete임이 아주 잘 알려져 있다. 심지어 $O(n^{0.99})$-factor로 approximate할 수 있으면 $\textsf{NP} = \textsf{ZPP}$ 이다 (사실상 $\textsf{P} = \textsf{NP}$ 라는 뜻이다.) 어차피 제대로 못 푸는 문제이니 대신 다음과 같은 그리디 알고리즘을 생각해 볼 수 있다.

• 순열 $\pi$ 를 잡고, 그 순서대로 정점을 순회한다. $\pi$ 는 모든 길이 $n$ 의 순열 중 랜덤하게 샘플.
• 만약 현재 정점과 인접한 정점 중 $S$ 에 있는 정점이 없으면 현재 정점을 $S$ 에 넣는다. 아니면 패스.

위에서 설명한 이유 때문에 이 알고리즘이 최적해는 커녕 approximation도 못 함을 알 수 있지만, 이 알고리즘이 maximal independent set을 찾음은 알 수 있다. 다시 말해, 이 알고리즘이 리턴한 $S$에 정점 하나를 더 선택했을 경우 $S$ 는 independent set이 아니게 된다. 약간 local maxima같은 느낌이라고 보면 된다. Distributed Computing에서는 Maximal IS를 찾으면 $(\Delta + 1)$-coloring을 찾을 수 있다. 이 컨텍스트랑은 좀 다르지만 Maximal IS 자체도 그런 이유로 연구가 많이 되어 있다. Maximal IS를 dynamic하게 관리할 수 있으면 3-approx correlation clustering을 관리할 수 있다는 이상한 Corollary도 있었는데 (BDHSS19), 지금은 별 의미 없을 것 같다.

FOCS'19에 저 문제를 $O(\log^4 n)$ amortized에 푸는 논문이 2개 있었는데 (BDHSS19, Chechik, Zhang '19) 후자가 꽤 간단해 보여서 이 글에서 설명해 보려고 한다.

1. Intro

일단 문제가 아무 maximal independent set을 찾는게 아니라 저 순열 $\pi$ 에 대한 Greedy IS를 찾는 것임을 다시 강조한다. 이 문제를 LFMIS라고 부른다. (lexicographically first maximal independent set). 그리고 $\pi$ 는 모든 길이 $n$ 의 순열 중 랜덤하게 샘플되었다.

$(u, v)$ 를 잇는 간선이 추가되었다고 하자. 만약 $u, v$ 중 하나라도 LFMIS에 속하지 않으면 아무것도 안 해도 된다. $u, v$ 가 둘다 LFMIS에 속한다고 하고, $\pi(u) < \pi(v)$ 라고 하자. $u$ 는 아무것도 안 해도 되지만, $v$ 는 LFMIS에서 탈락된다. $v$ 가 LFMIS에서 탈락되면서 $v$ 에 인접한 다른 정점들이 LFMIS에 들어오게 될 수 있다. 그에 따라서 다른 정점들은 또 LFMIS에서 탈락될 수 있다. 이런 식으로 연쇄반응이 일어난다.

$(u, v)$ 를 잇는 간선이 제거되었다고 하자. $u, v$ 가 둘 다 LFMIS에 속하는 건 불가능하다. $u, v$ 가 둘 다 LFMIS에 속하지 않았다면 간선 제거 이후에도 속하지 않으니 아무것도 안 해도 된다. $\pi(u) < \pi(v)$ 라고 하자. $u$ 가 LFMIS에 속했다면, $v$ 는 간선 제거 이후 LFMIS에 추가될 여지가 있다. $v$ 가 LFMIS에 속했다면, 간선 제거 이후 $v$ 가 빠질 이유가 생기는 게 아니고 $u$ 가 들어갈 이유가 생기는 것도 아니다. 그래서 아무것도 안 해도 된다.

즉 일반성을 잃지 않고 $\pi(u) < \pi(v)$ 라고 하자. $pred_\pi(v)$ 를 $v$ 에 인접한 정점 중 $\pi(v)$ 보다 순서가 앞인 정점들의 집합이라고 하자. 그리고 LFMIS 집합을 $M$ 이라고 하면

• $(u, v)$ 를 잇는 간선이 추가되었고, ${u, v} \subseteq M$ 이면, $v$ 가 $M$ 에서 제거되어야 한다. 이후 연쇄반응이 있을 수 있다.
• $(u, v)$ 를 잇는 간선이 제거되었고, $u \in M$ 이고, $pred_\pi(v) \cap M = \emptyset$ 이면, $v$ 가 $M$ 에 추가된다. 이후 연쇄반응이 있을 수 있다.

연쇄반응이란 무엇일까? $M$ 이 올바른 LFMIS라는 것은 모든 정점 $v$ 에 대해 다음이 만족한다는 것이다:

• $v \in M$ 일 경우, $pred_\pi(v) \cap M = \emptyset$
• $v \notin M$ 일 경우, $pred_\pi(v) \cap M \neq \emptyset$

업데이트에 따라서 $v$ 가 위 조건을 만족하지 않게 된다면, $v$ 를 $M$ 에서 넣거나 빼야 한다. 이에 따라서 다른 정점들도 $M$ 에 들어가거나 빠지게 된다. $S$ 를, 현재 $M$ 에서의 상태가 확실하지 않은 정점들의 집합이라고 하자. 즉, $S$ 에 있는 정점들은 $M$ 에서의 상태가 바뀔 수 있으나, $S$에 없는 정점들은 추가 행동이 필요하지 않다. 위 업데이트에서 "연쇄반응" 이 필요해질 경우 초기 $S = {v}$ 로 초기화된다. 최종적으로, $S$ 는 다음 조건을 만족해야 한다:

• $v \in M$ 일 경우, $pred_\pi(v) \cap S = \emptyset$ iff $v \notin S$.
• $v \notin M$ 일 경우, $pred_\pi(v) \cap (M - S) \neq \emptyset$ iff $v \notin S$

어떠한 $v$ 가 저 조건을 만족하지 않는다면, $v$ 를 $S$ 에 넣어야 한다. 저 조건이 모든 정점에 대해 만족할때까지 $S$ 를 최대한으로 키우면, 이후 모든 갱신을 $S$ 에 한정해서 진행해도 된다.

2. $S$ 의 성질

놀랍게도 다음과 같은 사실이 성립한다:

Theorem 1. 임의의 그래프와 업데이트에 대해 $E[|S|] \le 1$. 기댓값은 모든 순열 $\pi$ 에 대해서 취해졌다.

이 사실을 이해하기 위해서는 $\pi, S$ 에 대한 몇가지 구조적 성질을 이해해야 한다. 먼저 정의를 소개한다.

• $S(\pi)$ 를, 현재 그래프와 업데이트를 순열 $\pi$ 에 대해 적용했을 때 반환되는 $S$ 라고 정의하자. 업데이트는 간선 $(u, v)$ 에 대해 적용되었으며 wlog $\pi(u) < \pi(v)$ 이다.
• $M_{old}(\pi)$ 를, 업데이트 전 현재 그래프에서 $\pi$ 에 대한 LFMIS로 정의하자.
• $M_{new}(\pi)$ 를, 업데이트 후 현재 그래프에서 $\pi$ 에 대한 LFMIS로 정의하자.
• $\pi_S$ 를, $\pi$ 에서 $S$ 에 속하는 원소들만 추려낸 부분수열로 정의하자.
• 수열 $a, b$ 에 대해 $a + b$ 는 두 수열의 concatenation이다.

Lemma 2. 임의의 그래프와 업데이트에 대해서, $S(\pi) \neq \emptyset$ 이라고 하자. $\pi_{V - S(\pi)} = \sigma_{V - S(\pi)}, \pi_{S(\pi)} = \sigma_{S(\pi)}$, $\sigma(u) < \sigma(v)$ 를 만족하는 모든 $\sigma$ 에 대해,

• $S(\sigma) = S(\pi)$
• $M_{old}(\sigma) = M_{old}(\pi)$

Proof. 만약에

• $\pi(x) + 1 = \pi(y)$ 이며 $x \in S(\pi), y \notin S(\pi)$ 인 임의의 두 $x, y$ 를 교환할 수 있거나
• $\pi(x) + 1 = \pi(y)$ 이며 $x \notin S(\pi), y \in S(\pi)$ 이며 $[x, y] \neq [u,v]$ 인 임의의 두 $x, y$ 를 교환할 수 있으면

버블 정렬의 요령으로 Lemma 2가 증명됨을 관찰하자. 고로 $\sigma$ 가 저러한 $(\pi(x), \pi(y))$ 를 교환해서 얻은 순열이라고 가정한다.

Part 1.
먼저 $M_{old}(\sigma) = M_{old}(\pi)$ 임을 증명한다. 정의에 따라, 집합 $M$ 이 LFMIS라는 것은 다음 조건이 성립한다는 것과 동치이다:

• $v \in M$ 일 경우, $pred_\pi(v) \cap M = \emptyset$
• $v \notin M$ 일 경우, $pred_\pi(v) \cap M \neq \emptyset$

$pred_\pi(v) = pred_\sigma(v)$ 가 모든 $v \notin {x, y}$ 에 대해서 성립하니, $v \in {x, y}$ 에 대해서만 해당 사실을 증명하면 된다. 만약 $x, y$ 간에 간선이 없다면, $pred_\pi(v) = pred_\sigma(v)$ 가 $x, y$ 에 대해서도 성립한다. 고로 $x, y$ 간에 간선이 있음을 가정하자. 증명은 $M_{old}(\sigma)$ 의 prefix에 대해 귀납적이다.

• $x \notin M_{old}(\pi), y \notin M_{old}(\pi)$: $pred_\pi(v) \cap M_{old}(\pi) = pred_\sigma(v) \cap M_{old}(\sigma)$ 이라 귀납 가정에 의해 자명.
• $x, y \in M_{old}(\pi)$: 간선이 있어서 가정에 모순.
• $x \notin M_{old}(\pi), y \in M_{old}(\pi)$:
  • $x \in S(\pi), y \notin S(\pi)$: $x \in pred_\pi(y) \cap S(\pi)$ 이기 때문에 $pred_\pi(y) \cap S(\pi) \neq \emptyset$ 이고, 따라서 $y \in S(\pi)$ 여야 하여 가정에 모순이다.
  • $x \notin S(\pi), y \in S(\pi)$: $pred_\sigma(y) \subseteq pred_\pi(y)$ 이니 $y \in M_{old}(\sigma)$ 이다. $pred_\sigma(x) \supseteq pred_\pi(x)$ 이니 $x \notin M_{old}(\sigma)$ 이다.
• $x \in M_{old}(\pi), y \notin M_{old}(\pi)$:
  • $x \in S(\pi), y \notin S(\pi)$: $pred_\pi(y) \cap (M_{old}(\pi) - S(\pi))$ 가 비지 않았다. 여기 속하는 $z$ 는 $x$ 가 아니니, $pred_\sigma(y) \cap M_{old}(\sigma)$ 에 속한다. 고로 $y \notin M_{old}(\sigma)$ 이다. $y \notin M_{old}(\sigma)$ 이니 $x \in M_{old}(\sigma)$ 이다.
  • $x \notin S(\pi),y \in S(\pi)$: $pred_\pi(y) \cap (M_{old}(\pi) - S(\pi))$ 가 비었다. 하지만 $x \in pred_\pi(y) \cap (M_{old}(\pi) - S(\pi))$ 이다. 고로 가정에 모순이다.

Part 2.
다음으로, $S(\sigma) \supseteq S(\pi)$ 임을 증명한다. $S$ 는 처음에 정점 $v$ 를 추가하는 것에서부터 시작하여 귀납적으로 정의된다. 이 과정에 대해 귀납법을 적용하여, $S(\pi)$ 에 들어가는 모든 정점은 $S(\sigma)$ 에도 들어감을 보인다. $M =M_{old}(\sigma) = M_{old}(\pi)$ 를 뜻한다.

• Base case: $v \in S(\sigma)$ 임을 보이면 된다. $M_{old}(\sigma) = M_{old}(\pi)$, $\sigma(u) < \sigma(v)$ 이다. 고로 간선 추가의 경우는 정의상 자명하다. 간선 삭제를 생각해 보자. 만약 $pred_\sigma(v) \cap M = {u}$ 인 경우 역시 자명하다. $u$ 는 위 집합에서 사라질 수 없으니 저것이 성립하지 않을 수 있는 유일한 경우는 $\sigma$ 에서 $v, w$ 가 스왑된 후 $pred_\sigma(v) \cap M = {u, w}$ 가 성립할 때이다. 이 경우, $v \notin M, w \in M$ 이며 $v \in S(\pi), w \notin S(\pi)$ 이다. $pred_\pi(w) \cap S(\pi) \neq \emptyset$ 이라 $w \in S(\pi)$ 여야 하여 가정에 모순이다.
• Inductive case: $S(\pi)$ 에 새로 들어간 정점 $z$ 를 생각해 보자. 케이스가 두 가지로 나뉜다. $S$ 는 $z$ 가 들어가기 직전의 $S(\pi)$ 를 뜻한다.
  • $z \in M$: $pred_\pi(z) \cap S$ 가 비지 않았다. ${z} \cup S$ 의 순서는 $\pi$ 와 $\sigma$ 에서 모두 보존되니, $pred_\sigma(z) \cap S = pred_\pi(z) \cap S$ 라서 $v \in S(\sigma)$ 가 성립한다.
  • $z \notin M$: $pred_\pi(z) \cap M = pred_\sigma(z) \cap M$ 임을 증명하면 된다. $z \notin {x, y}$ 일 경우 바로 성립한다. $z = x$ 인 경우를 보자. 이 경우 둘이 달라지기 위해서는 $y \in M$ 이며 $(x, y)$ 간에 간선이 있어야 한다. $y \notin S(\pi)$ 이니, $pred_\pi(y) \cap S(\pi) = \emptyset$ 이다. $x \in pred_\pi(y) \cap S(\pi)$ 이니 가정에 모순이다. $z = y$ 인 경우도 동일하게 증명된다.

Part 3.
마지막으로, $S(\sigma) = S(\pi)$ 임을 증명한다. $S$ 가 만족해야 할 조건을 생각해 보자:

• $v \in M$ 일 경우, $pred_\pi(v) \cap S = \emptyset$ iff $v \notin S$.
• $v \notin M$ 일 경우, $pred_\pi(v) \cap (M - S) \neq \emptyset$ iff $v \notin S$

만약

• $v \in M$ 일 경우, $pred_\sigma(v) \cap S(\pi) = \emptyset$ iff $v \notin S(\pi)$
• $v \notin M$ 일 경우, $pred_\sigma(v) \cap (M - S(\pi)) \neq \emptyset$ iff $v \notin S(\pi)$

가 성립할 경우 $S(\sigma) = S(\pi)$ 임을 볼 수 있다. Part 2에서 $S(\sigma) \supseteq S(\pi)$ 임을 보였기 때문이다. $pred_\pi(v) = pred_\sigma(v)$ 가 모든 $v \notin {x, y}$ 에 대해서 성립하니, $v \in {x, y}$ 에 대해서만 해당 사실을 증명하면 된다. 만약 $x, y$ 간에 간선이 없다면, $pred_\pi(v) = pred_\sigma(v)$ 가 $x, y$ 에 대해서도 성립한다. 고로 $x, y$ 간에 간선이 있음을 가정하자.

• $x \notin M, y \notin M$: $pred_\pi(v) \cap M = pred_\sigma(v) \cap M$ 이라 자명
• $x, y\in M$: 간선이 있어서 가정에 모순.
• $x \notin M, y \in M$:
  • $x \in S(\pi), y \notin S(\pi)$: $x \in pred_\pi(y) \cap S(\pi)$ 이기 때문에 $pred_\pi(y) \cap S(\pi) \neq \emptyset$ 이고, 따라서 $y \in S(\pi)$ 여야 하여 가정에 모순.
  • $x \notin S(\pi), y \in S(\pi)$: $pred_\pi(x) \cap (M - S(\pi)) \neq \emptyset$ 이면 $pred_\sigma(x) \cap (M - S(\pi)) \neq \emptyset$ 이다. $pred_\pi(y) \cap S(\pi) \neq \emptyset$ 이면 $pred_\sigma(y) \cap S(\pi) \neq \emptyset$ 이다.
• $x \in M, y\notin M$:
  • $x \in S(\pi), y \notin S(\pi)$: $pred_\sigma(x) \cap S(\pi) = pred_\pi(x) \cap S(\pi)$ 이며 $pred_\pi(y) \cap (M - S(\pi)) = pred_\sigma(y) \cap (M - S(\pi))$ 이다.
  • $x \notin S(\pi), y \in S(\pi)$: $y \notin M$ 이기 때문에 $pred_\pi(y) \cap (M - S(\pi)) = \emptyset$ 이어야 하는데, $x \in pred_\pi(y) \cap (M - S(\pi))$.

$\blacksquare$

Lemma 3. 임의의 그래프와 업데이트에 대해서, $S(\pi) \neq \emptyset$ 이라고 하자. $\pi_{V - S(\pi)} = \sigma_{V - S(\pi)}, \pi_{S(\pi) - {v}} = \sigma_{S(\pi) - {v}}$, $\sigma(u) < \sigma(v)$ 를 만족하는 모든 $\sigma$ 에 대해, 만약 $\sigma_{S(\pi)}$ 의 첫 원소가 $v$ 라면 $S(\sigma) = S(\pi)$ 이고, 그렇지 않다면 $S(\sigma) = \emptyset$ 이다.

Proof. 첫 원소가 $v$ 인 경우는 Lemma 2에 의해 자명하다. $\pi$ 를, $\sigma_{S(\pi)}$ 에서 $v$ 를 포함하는 prefix를 cyclic shift해서 $v$ 를 맨 앞으로 돌린 순열이라고 하자. 이 $\pi$ 에 대해서만 증명할 수 있다면, Lemma 2에 의해 모든 $\pi$ 에 대해서 증명할 수 있다. $\pi_{S(\pi)} = [v, w, \ldots]$ 라고 하자. $\sigma_{S(\pi)}$ 의 첫 원소는 $w$ 이다. $w$ 와 $v$ 간에 간선이 없다면 $w \notin S(\pi)$ 이기 때문에 $(v, w)$ 사이에 간선이 존재한다. 임의의 업데이트 후, $w$ 가 항상 $M(\sigma)$ 에 속하거나, $S(\sigma) = \emptyset$ 임을 증명할 수 있다. $S(\sigma) \neq \emptyset$ 가 가능한 업데이트 두 종류를 살펴보자:

• $(u, v)$ 사이에 간선이 추가되었다고 하자. $v \in M(\pi)$ 였으니, $w \notin M(\pi)$ 이고 $pred_\pi(w) \cap (M - S(\pi)) = \emptyset$ 이다. 따라서 $pred_\pi(w) \cap M \subseteq {v}$ 이고, $pred_\sigma(w) \cap M = \emptyset$ 이다. 고로 $w \in M(\sigma)$ 이다.
• $(u, v)$ 사이에 간선이 제거되었다고 하자. $u \in M(\pi)$, $v \notin M(\pi)$, $pred_\pi(v) \cap M(\pi) = \emptyset$ (업데이트 후) 이다. $w$ 가 $v$ 에서의 연쇄 반응의 즉각적 결과면, $w$ 는 업데이트 전 $M(\pi)$ 에 속한다. 즉, $pred_\pi(w) \cap M(\pi) = \emptyset$ 이다. $pred_\sigma(w)\subseteq pred_\pi(w)$ 이며, $M(\sigma)$ 는 $w$ 의 위치 전까지는 모두 $M(\pi)$ 와 일치하니, $w \in M(\sigma)$ 이다. $\sigma$ 에 대한 업데이트는 $w$ 뒤 정점 $v$ 만 영향을 끼치니 업데이트 후에도 성립한다.

따라서 $w \in M(\sigma)$ 이다. 이에 따라서 $v \notin M(\sigma)$ 이며 $w \in pred_{\sigma}(v) \cap M(\sigma)$ 이다. 고로 어떤 업데이트도 $v$ 를 $S$ 에 넣을 수 없다. $\blacksquare$

이제 Main Theorem을 증명할 준비가 되었다.

Proof of Theorem 1. 업데이트가 두 정점 $(u, v)$ 사이에 이루어졌다고 하자 ($\pi(u) < \pi(v)$). $S(\pi) \neq \emptyset$ 인 모든 $\pi$ 에 대해서, 다음 집합 $Rot(\pi)$ 를 선언한다:

$Rot(\pi) = {\pi^\prime | \pi^\prime_{S(\pi) \setminus {v}} = \pi_{S(\pi) \setminus {v}}, \pi^\prime_{V \setminus S(\pi)} = \pi_{V \setminus S(\pi)}, \pi^\prime(u) < \min_{w \in S(\pi)} \pi^\prime(w) }$

먼저, $E[|S(\pi^\prime)| \mid \pi^\prime \in Rot(\pi)] = 1$ 임을 증명하자. $\pi$ 가 주어졌을 때, $V \setminus S(\pi)$ 가 등장하는 위치를 모두 고정하자. 이 위치가 고정되면, $u$ 와 나머지 $S(\pi)$ 가 어디 등장하는지가 고정되기 때문에, 조건 $\pi^\prime(u) < \min_{w \in S(\pi)} \pi^\prime(w)$ 가 성립하는지 아닌지가 결정된다. 이제 남은 위치에서 $v$ 를 맨 앞에 넣으면 $S(\pi^\prime) = S(\pi)$ 이고, 아니면 $S(\pi^\prime) = \emptyset$ 이다. 맨 앞에 넣을 확률이 정확히 $1/|S(\pi)|$ 이니 기댓값은 $1$ 이다.

이제, 서로 다른 두 순열 $\pi_1, \pi_2$ ($S(\pi_1) \neq \emptyset, S(\pi_2) \neq \emptyset$) 에 대해서 $Rot(\pi_1) = Rot(\pi_2)$ 이거나 $Rot(\pi_1) \cap Rot(\pi_2) = \emptyset$ 임을 보인다. 이것이 사실이라면, 모든 순열은 최대 하나의 서로 다른 $Rot$ 에 속하거나, 전혀 안 속하기 때문에 Theorem 1이 증명된다.

어떤 순열 $\tau$ 가 $Rot(\pi_1) \cap Rot(\pi_2)$ 에 속한다고 하자. $\tau$에서 $v$ 를 빼다가 $u$ 의 바로 뒤에 배정하는 연산을 해도, $\tau$ 는 $Rot(\pi_1) \cap Rot(\pi_2)$ 에 그대로 속한다. $\pi_1$ 에서 $v$ 는 $S(\pi_1)$ 의 맨 앞에 배정되어 있고, 그건 $\tau$ 에서도 마찬가지이니, Lemma 2에 의해서 $S(\pi_1) = S(\tau)$ 이다. 동일한 이유로 $S(\pi_2) = S(\tau)$ 이다. 그리고 $\tau_{S(\tau)} = \pi_{S(\pi_1)}= \pi_{S(\pi_2)}, \tau_{V \setminus S(\tau)} = \pi_{V \setminus S(\pi_1)}= \pi_{V \setminus S(\pi_2)}$ 이다. 따라서 $Rot(\pi_1) = Rot(\pi_2)$ 이다. $\blacksquare$

유사한 방식으로 다음을 증명할 수 있다. 이건 당장 필요하진 않다.

Theorem 4. 임의의 그래프와 업데이트, 그리고 인자 $1 \le C \le A < B \le n$ 에 대해, 대해 $E[|S|] < \frac{n}{B - A}$. 기댓값은 다음을 만족하는 모든 순열 $\pi$ 에 대해 취해졌다: $\pi(u) = C, \pi(v) \in [A+1, B]$.

Proof of Theorem 4. $\mathcal{E} = {\pi|\pi(u) = C, \pi(v) \in [A+1, B]}$ 라 하자. $S(\pi) \neq \emptyset$ 이며 모든 $\pi$ 에 대해서, 다음 집합 $Rot(\pi)$ 를 선언한다:

$Rot(\pi) = {\pi^\prime | \pi^\prime \in \mathcal{E}, \pi^\prime_{S(\pi) \setminus {v}} = \pi_{S(\pi) \setminus {v}}, \pi^\prime_{V \setminus S(\pi)} = \pi_{V \setminus S(\pi)}, A < \min_{w \in S(\pi)} \pi^\prime(w) }$

$E[|S(\pi^\prime)| \mid \pi^\prime \in Rot(\pi)]$ 를 계산하자. 고정된 $\pi$ 에 대해서 $S(\pi)$ 를 올바르게 배정하는 방법은 $(B - A) \times \binom{n - A - 1}{|S| - 1}$ 가지이다. 이 중 $S(\pi)$ 가 비지 않으려면 $v$ 가 맨 앞에 와야 한다. 이를 만족하는 배정의 개수는 $\binom{n - A}{|S|} - \binom{n - B}{|S|}$ 이다. 즉, 기댓값은 $|S| \frac{\binom{n - A}{|S|} - \binom{n - B}{|S|}}{(B - A) \binom{n - A - 1}{|S| - 1}} < \frac{n}{B - A}$ 이다.
이제, 서로 다른 두 순열 $\pi_1, \pi_2$ ($S(\pi_1) \neq \emptyset, S(\pi_2) \neq \emptyset$) 에 대해서 $Rot(\pi_1) = Rot(\pi_2)$ 이거나 $Rot(\pi_1) \cap Rot(\pi_2) = \emptyset$ 임을 보인다. Theorem 1과 동일하게 하는데 $v$ 를 $A+1$ 번째 위치에 배정하면 된다.

Theorem 5. 임의의 그래프와 업데이트, 그리고 인자 $1 \le A < B \le n$ 에 대해, 대해 $E[|S|] < \frac{2n}{B - A+1}$. 기댓값은 다음을 만족하는 모든 순열 $\pi$ 에 대해 취해졌다: $A \le \pi(u) < \pi(v) \le B$.

Proof of Theorem 5. 임의의 $X \neq Y$ 에 대해서 $\pi(u) = X, \pi(v) = Y$ 일 확률은 모두 균등하다. 고로 모든 가능한 $A \le X < Y \le B$ 에 대해서 Theorem 4를 사용하여 기댓값을 구하고 합하면 된다. 계산하면 $\sum_{X = A}^{B} \frac{B - X}{(B-A+1)(B-A)/2} \frac{n}{B - X} < \frac{2n}{B - A + 1}$ 이다.

3. $E[|S|] \le 1$ 임만을 사용한 알고리즘

$|S|$ 의 크기가 작다는 것만으로 효율적인 알고리즘을 얻을 수는 없다. 다만 그래프의 최대 차수가 $\Delta$ 일 경우, $O(|S| \cdot \Delta)$ 시간에 작동하는 알고리즘을 얻을 수는 있다. $|S|$ 의 기댓값이 $1$ 이니 이것만으로 쿼리당 expected $O(\Delta)$ 시간에 작동하는 알고리즘을 얻는다.

알고리즘은 다음과 같다. 초기 $O(\Delta)$ 시간을 소비해서 $v \in S$ 인지를 판별한다. $v \in S$ 라면 $S$ 에 새로운 정점 $v$ 가 삽입되어야 한다. 새로운 정점이 $S$ 에 삽입되면 다음과 같이 추가 삽입이 필요한지를 결정한다:

• $v$ 랑 인접하면서 $\pi(w) > \pi(v)$ 인 정점들을 모두 순회한다.
  • 만약 $w \in M$ 이라면, $w$ 를 $S$ 에 삽입한다.
  • 만약 $w \notin M$ 이고 $v \in M$ 이라면, $w$ 의 카운트를 증가시킨다. 이 카운트가 $|pred_\pi(w) \cap M|$ 과 일치하게 되면, $w$ 를 $S$ 에 삽입한다.

각 정점이 삽입되는데 $O(\Delta)$ 시간이 소모되니 expected $O(\Delta) = O(n)$ 시간에 알고리즘이 작동함을 볼 수 있다. 이제 $S$ 에 있는 정점들의 상태를 변경해야 한다. Lemma 2에 의해서, $S$ 안에 있는 정점들의 상대 순서만 유지할 수 있으면, $\pi_S$ 가 $\pi$ 의 suffix라고 생각해도 무방하다. 고로 $S$ 에 있는 정점들을 순서대로 돌면서, 기존 $M$ 을 거스르지 않고 갱신해 주면 된다. 갱신 이후 $|pred_\pi(w) \cap M|$ 카운터를 갱신에 맞게 조정해 주면 끝이다.

4. 차수 줄이기

첫 알고리즘을 개선하는 방법은 그래프의 차수를 줄이는 것이다. 이게 무슨 말인지를 다음 Lemma를 통해 설명한다.

Lemma 6. $G_i$ 를, 그래프 $G$ 에서 $\pi(1), \pi(2), \ldots, \pi(i)$ 까지에 대해서 Greedy MIS를 구한 이후 남은 그래프라고 하자. 구체적으로, $G_i$ 는 $\pi(i) \notin M$ 이면 $G_{i-1}$ 이고, $\pi(i) \in M$ 이면 $G_{i-1}$ 에서 $\pi(i)$ 와 그에 인접한 정점을 모두 지운 그래프이다. $1 - n^{-9}$ 이상의 확률로 $G_i$ 의 최대 차수는 $\frac{10 n \log n}{i}$ 이하이다.

Proof. $v \in G_i$ 에 대해서, $v$ 의 최대 차수가 $\frac{10 n \log n}{i}$ 를 초과할 확률을 계산하자. 이는 $v$ 에 인접한 정점이 모두 $\pi$ 에서 $i+1$ 번째 이후로 등장한다는 것과 동치이다. $(1 - \frac{i}{n})^{n/i \times 10 \log n} \le n^{-10}$ 이니, union bound에 따라 $1 - n^{-9}$ 의 확률로 $G_i$ 의 최대 차수는 $\frac{10 n \log n}{i}$ 이하이다.

적당한 $1 \le k \le n$ 에 대해서, $G_k$ 를 explicit하게 관리하자. 업데이트가 들어오면 다음과 같이 처리한다:

• 만약 양 끝점 중 하나가 $\pi(1), \pi(2), \ldots, \pi(k)$ 에 속한다면, $O(m)$ 시간에 전부 새로 계산한다.
• 만약 양 끝점 모두가 $\pi(k+1), \ldots, \pi(n)$ 에 속한다면, $\tilde{O}(n / k)$ 시간에 위에서 말한 알고리즘대로 갱신해준다.

재계산이 일어나는 확률은 $\frac{k}{n}$ 이니, 이 알고리즘은 $\tilde{O}(m \frac{k}{n} + \frac{n}{k})$ 시간에 동작한다. $k = \frac{n}{\sqrt m}$ 으로 잡으면, $\tilde{O}(\sqrt m)$ 에 각 쿼리를 해결할 수 있다.

5. 자료구조 -- 구성 및 정당성

$O(\log^4 n)$ 시간에 문제를 해결해 보자. 관리하는 자료구조는 사실 앞의 알고리즘과 크게 다르지 않다. 자료구조는, 모든 $0 \le i \le \log n - 1$ 에 대해서, $G_{0} \supseteq G_{1} \supseteq G_{2} \supseteq \ldots \supseteq G_{\log n - 1}$ 을 관리한다. 여기서 $G_i$는, 그래프 $G$ 에서 $\pi(1), \pi(2), \ldots, \pi(2^i - 1)$ 까지에 대해서 Greedy MIS를 구한 이후 남은 그래프이다. (Lemma 6과 다른 정의를 overload하였다.)

$G_i$ 를 관리한다는 것은 말 그대로 induced subgraph 그 자체를 통으로 관리한다는 것이다. 즉 정점 집합이 있고 각 정점 집합에 인접 리스트 (해시 테이블) 로 간선이 표현된 형태이다. 이렇게 Naive한 표현만으로 전체 문제를 해결할 수 있다.

간선이 추가되는 케이스를 살펴보자. $\pi(u) < \pi(v)$ 이다. 또한 $\pi(u) \in [2^a, 2^{a+1} - 1], \pi(v) \in [2^b, 2^{b+1}- 1]$ 이다.

1. $u \notin M$: $V_i$ 가 전혀 바뀌지 않는다. 그냥 ${u, v} \subseteq V_i$ 인 $G_i$ 에 간선을 추가한다.
2. $u \in M, v \notin M$: $v$ 는 $u$ 에 dominate되니, $V_{a+1}, \ldots, V_{\log n - 1}$ 에서 $v$ 를 제거한다. 이 과정에서 인접한 간선들도 제거될 수 있다. 이후 ${u, v} \subseteq V_i$ 인 $G_i$ 에 간선을 추가한다.
3. $u \in M, v \in M$: 실제로 MIS가 바뀌는 경우로 이후 설명한다.

간선이 제거되는 케이스를 살펴보자. $\pi(u) < \pi(v)$ 이다. 또한 $\pi(u) \in [2^a, 2^{a+1} - 1], \pi(v) \in [2^b, 2^{b+1} - 1]$ 이다.

1. $u \notin M$: $V_i$ 가 전혀 바뀌지 않는다. 그냥 ${u, v} \subseteq V_i$ 인 $G_i$ 에 간선을 제거한다.
2. $u \in M, v \notin M, pred_\pi(v) \cap M \neq {u}$: 일단 ${u, v} \subseteq V_i$ 인 $G_i$ 에 간선을 제거한다. $V_{a+1}, \ldots, V_{\log n - 1}$ 에서 $v$ 가 $u$ 에만 dominate되었다면, 부활할 가능성이 존재한다. $v \notin V_{a}$ 일 경우 이는 불가능하다. 그렇지 않은 경우 $V_{a}$ 의 이웃들을 모두 순회하면서 $v$ 가 dominate되는 첫 시점을 찾고 이에 맞게 맞는 그래프에 정점 $v$ 와 대응되는 이웃을 추가한다.
3. $u \in M, v \notin M, pred_\pi(v) \cap M = {u}$: 실제로 MIS가 바뀌는 경우로 이후 설명한다.

추가/제거 모두에 대해서 1번 케이스는 $O(\log n)$ 시간에 가능하다. 2번 케이스는 $\frac{2^a}{n}$ 의 확률로 $O(\frac{n}{2^a} \log n)$ 의 시간을 사용한다. 후자는 whp로 보장되니 곱하면 $O(\log n)$ 시간이다. 고로 이 두 케이스는 무시하고 3번 케이스만 고려한다.

3번 케이스의 경우 $S(\pi) \neq \emptyset$ 이다. 고로 해야 할 일은:

• $S(\pi)$ 를 계산
• $S(\pi)$ 안에서 $M$ 이 어떻게 갱신되는지 확인하고 이를 자료구조에 반영

5.1. $S(\pi)$ 계산하기

규칙을 다시 상기해보면:

• $v \in M$ 일 경우, $pred_\pi(v) \cap S \neq \emptyset$ iff $v \in S$
• $v \notin M$ 일 경우, $pred_\pi(v) \cap (M - S) = \emptyset$ iff $v \in S$

한 가지 알아둘 것은 $S \subseteq V_b$ 라는 것이다. $S - V_b$ 에 속하는 정점이 있다면 이는 절대 $M$ 에 속할 수는 없고, $M$ 에 이웃한 정점일텐데 그렇게 되면 $pred_\pi(v) \cap (M - S)$ 가 빌 수 없다.

우선순위 큐 $T$를 관리하자. $T$는 $S$에 들어갈 수 있는 후보 정점을 $\pi(v)$ 순으로 관리한다. 초기에는 $T = {v}$ 로 시작하며, $T$ 가 비지 않을 때까지 다음을 반복한다:

• $\pi(v)$ 를 최소화하는 $z$ 를 $T$ 에서 뽑는다. 이미 처리한 정점이면 넘어간다.
• 만약 $z \in M$ 이면
  • $pred_\pi(z) \cap S \neq \emptyset$ 이라서 들어갔을 것이기 때문에 $z$ 를 $S$ 에 삽입한다.
  • $\pi(z) \in [2^k, 2^{k+1} - 1]$ 이라고 하자. 정의상 $z \in V_k$ 이다.
  • $V_k$ 에서 $\pi(w) > \pi(z)$ 인 모든 이웃 $w$ 를 $T$ 에 넣는다.
    • $V_b$ 를 안 봐도 되는 이유는, $(V_b - V_k) \cap M$ 은 어차피 우선순위가 더 낮고, $(V_b - V_k) \setminus M$ 은 (a) $M \setminus S$ 에 속하는 이웃한테 dominate당해서, 어차피 못 올라오거나 (b) $M \cap S$ 에 속하는 이웃한테 dominate당해서, 그러한 이웃 중 $\pi$ 가 최소화되는 이웃을 보는 시점에 이미 $T$ 에 들어갔기 때문이다. (다시 말해, $pred_\pi(w) \cap M \subseteq S$ 를 만족하는 $w \in V_b$ 라면, 저 원소 중 첫 원소가 $S$ 에 들어갈 때 그 시점의 $V_k$ 에서는 무조건 살아 있고, 그래서 그 시점에 처리된다.)
• 아니면
  • $pred_\pi(z) \cap (M - S) = \emptyset$ 인지를 확인해야 한다. 이를 위해:
  • $V_b$ 에서 $\pi(w) < \pi(z)$ 인 모든 이웃 $w$ 를 보고, 이 중 $M-S$ 에 속하는 이웃이 있는지 확인한다. 이러한 이웃이 있으면 넘어간다.
    • $V$ 에서 볼 필요는 없다. $(V - V_b) \cap M$ 이 비지 않았다면 어차피 $z \notin V_b$ 이다.
  • 아니면 $z$ 를 $S$ 에 삽입하고, $V_b$ 에서 $\pi(w) > \pi(z)$ 인 모든 이웃 $w$ 를 $T$ 에 넣는다.

알고리즘에서 자명하지 않은 부분은 이미 다 설명했으니 $S(\pi)$ 는 올바르게 계산됨을 볼 수 있다. $T_0$ 을 $T$ 에 한번이라도 존재했던 정점의 개수라고 하면, 알고리즘의 시간 복잡도는 $|T_0| \cdot O(\frac{n \log n}{2^b})$ 이다. $|T_0|$ 의 상한은 이후 다룬다.

5.2. $M$ 갱신하기

$S(\pi)$ 를 계산했으니, 인접 리스트에 간선을 추가/제거하고, 실제 $M$ 이 어떻게 갱신되는지를 계산하자. $S(\pi)$ 에 있는 정점들을 $\pi(v)$ 순서대로 순회한다.

• 먼저 $v$ 는 확실히 $M$ 에서 위치를 바꾼다.
• $z \notin M$ 일 경우, $pred_\pi(z) \cap M \subseteq S$ 이다. 고로 $pred_\pi(z) \cap S$ 에서 $M$ 에 속하는 원소가 있는지를 확인하면 된다.
• $z \in M$ 일 경우, $pred_\pi(z) \cap (M - S)$ 는 어차피 갱신이 없으니 역시 $pred_\pi(z) \cap S$ 에서 $M$ 에 속하는 원소가 있는지를 확인하면 된다.

따라서 $S(\pi)$ 의 induced subgraph만 가지고도 MIS를 확인할 수 있다. 사실 $S(\pi)$ 의 induced subgraph에서 LFMIS를 구하는 것과 동치이고, $S(\pi)$ 밖은 신경쓸 필요가 없다. induced subgraph는 $V_b$ 에 포함되어 있으니 이를 통해 $|S(\pi)| \cdot O(\frac{n \log n}{2^b}) \le |T_0| \cdot O(\frac{n \log n}{2^b})$ 시간에 구할 수 있다.

$S(\pi)$ 에서 갱신되는 모든 정점 $v$ ($\pi(v) \in [2^{k}, 2^{k+1} - 1]$) 에 대해:

• $v$ 가 새롭게 $M$ 에 들어가게 된다면, $G_{k+1}, G_{k+2}, \ldots$ 에 대해 $v$ 와 $v$ 의 이웃을 모두 제거한다. $v$ 의 이웃은 $V_k$ 에 있는 것을 순회하면 된다.
• $v$ 가 $M$ 을 떠나게 된다면, $v$ 와 $v$ 의 이웃이 부활할 가능성이 존재한다. 이 정점들이 $V_k$ 에 속하지 않을 경우 이는 불가능하다. 그렇지 않은 경우 $V_{k}$ 의 이웃들을 모두 순회하면서 해당 정점이 dominate되는 첫 시점을 찾고 이에 맞게 맞는 그래프에 정점 $v$ 와 대응되는 이웃을 추가한다.

$T_1$ 을, 여기서 순회된 $v$ 와 $v$ 의 이웃들의 개수 합이라고 하자. 정점의 추가/제거는 $O(\frac{n \log n}{2^b})$ 시간에 할 수 있으니, 이 알고리즘은 $|T_1| \cdot O(\frac{n \log n}{2^b})$ 시간에 작동한다.

이제 알고리즘 전체의 설명이 끝났다. 이 알고리즘이 왜 효율적인지 알아보자.

6. 시간 복잡도 분석

크게 네 단계가 있다.

• $|S(\pi)|$ 의 크기 bound.
• $|T_0|$ 의 크기를 $O(|S(\pi)| \log^2 n)$ 으로 bound.
• $|T_1|$ 의 크기를 $O(|S(\pi)| \log^2 n)$ 으로 bound.
• 모두 합치기

여기서 $\pi$ 의 확률 공간은 $\mathcal{E} = {\pi \mid \pi(u) < \pi(v), \pi(u) \in [2^a, 2^{a+1} - 1], \pi(v) \in [2^b, 2^{b+1}- 1]}$ 에서 uniform randomly이다.

첫 번째 단계는 아주 간단하다.

Lemma 7. $E[|S(\pi)|] \le O(\frac{n}{2^b})$.
Proof. Theorem 4/5에 의해 자명.

이제 두 번째 단계로 넘어간다. $\Omega_{\pi} = {\pi^\prime \mid S(\pi^\prime) = S(\pi), \pi_{S(\pi)} = \pi^\prime_{S(\pi)}, \pi_{V -S(\pi)} = \pi^\prime_{V -S(\pi)}, \pi^\prime \in \mathcal{E}}$ 로 정의하자. 먼저 $E[|T_0| \mid \Omega_\pi]$ 를 bound하면서 시작할 것이다. 다음과 같은 사실들을 사용한다.

• 임의의 $\sigma \in \Omega_\pi$ 에 대해 $S(\sigma) = S(\pi)$ 이며 $M_{old}(\sigma) = M_{old}(\pi)$ (Lemma 2)
• 임의의 $\sigma \in \Omega_\pi$ 에 대해 $\sigma(v) \leq \min_{w \in T_0} \sigma(w)$ (알고리즘에 의해 자명)

Lemma 8. 임의의 $k > b$ 에 대해서, $E[|(S \setminus {v}) \cap \sigma[2^b, 2^k-1]| \mid \sigma \in \Omega_\pi] < \frac{2^k|S|}{n}$
Proof. $\sigma(v) \in [2^b, 2^{b+1} - 1]$ 이다. $\sigma(v)$ 의 위치를 $j$ 로 고정하자. 그러면 $j + 1, \ldots, n$ 에서 $|S| - 1$ 개를 뽑는 각 조합과 $\Omega_\pi$ 에 있는 순열 간에 일대일 대응이 가능하다. 이 중 $j + 1, \ldots, 2^k - 1$ 에서 뽑힌 위치의 기댓값을 계산해야 한다. 그 기댓값은 $\frac{2^k - 1 - j}{n - j} (|S| - 1)$ 이고 이는 $\frac{2^k}{n}|S|$ 미만이다.

Lemma 9. $E[|T_0| \mid \Omega_\pi] \le O(|S| \log^2 n) + O(n \log n /2^b)$
Proof. $E[|T_0 \setminus S| \mid \Omega_\pi] \le O(|S| \log^2 n) + O(n \log n /2^b)$ 을 증명하면 된다. $T_0 \setminus S$ 의 원소들은 모두 5.1의 알고리즘에 따라서 $V \setminus M$ 에 속한다. $V \setminus M$ 에 있는 원소가 $T_0$ 에 들어갈 가능성은, $z \in M$ 인 원소를 처리할 때 $V_k$ 에 속하는 모든 이웃을 넣는 과정 뿐이다. 즉, $T_0 \setminus S$ 의 크기는, $S$ 를 이루는 각 원소들의 $O(\frac{n \log n}{2^k})$ 의 합으로 upper bound된다. Lemma 1에 의해, $E[|S \setminus {v} \cap \sigma[2^{k-1}, 2^k - 1]| \mid \sigma \in \Omega_\pi] < \frac{2^k|S|}{n}$ 이다. 고로 $S \setminus {v}$ 를 이루는 각 원소들의 $O(\frac{n \log n}{2^k})$ 의 합은 $O(|S| \log^2 n)$ 이다. $v$ 에서 $O(n \log n/2^b)$ 개의 이웃을 넣으니 합하면 Lemma 9가 증명된다.

세번째 단계는 두 번째 단계랑 똑같이 하면 된다.

Lemma 10. $E[|T_1| \mid \Omega_\pi] \le O(|S| \log^2 n) + O(n \log n /2^b)$
Proof. $T_1$ 의 크기는, $S$ 를 이루는 각 원소들의 $O(\frac{n \log n}{2^k})$ 의 합으로 upper bound된다. 고로 Lemma 9의 증명을 그대로 사용하면 된다.

이제 최종 Theorem을 증명할 수 있다.

Theorem 11. 알고리즘은 expected $O(\log^4 n)$ 시간에 작동한다.
Proof. Lemma 9/10에 의해 $E[|T_0 \cup T_1| \mid \Omega_\pi] \le O(|S| \log^2 n) + O(n \log n/2^b)$ 이다. 또한 $\Omega_\pi$ 는 항상 동일한 집합이거나 서로소 집합이다. Theorem 4의 증명을 사용해도 되고, 더 간단하게 얘기하면 $S(\pi) \neq \emptyset$ 인 모든 $\pi$ 에 대해, $\Omega_\pi$ 는 equivalence class를 이룬다. ($V\setminus S$ 다음에 $S$ 가 오도록 정렬하는 canonical form을 이룰 수 있기 때문). 고로 서로 다른 $\Omega_\pi$ 들에 대해서 다음을 구하면 된다:

$\sum_{\Omega_\pi} E[|T_0 \cup T_1| \mid \Omega_\pi] \cdot Pr[\pi \in \Omega_\pi \mid \pi \in \mathcal{E}]$

정리하면:

$\sum_{\Omega_\pi} E[|T_0 \cup T_1| \mid \Omega_\pi] \cdot Pr[\pi \in \Omega_\pi \mid \pi \in \mathcal{E}]$
$\le \sum_{\Omega_\pi} O(|S(\pi)| \log^2 n + n \log n / 2^b) \cdot Pr[\pi \in \Omega_\pi \mid \pi \in \mathcal{E}]$
$\le O(n \log n /2^b) + \sum_{\Omega_\pi} O(|S(\pi)| \cdot Pr[\pi \in \Omega_\pi \mid \pi \in \mathcal{E}] \cdot \log^2 n)$
$\le O(n \log n / 2^b) + O(n \log^2 n / 2^b)$ (by Lemma 7)
$\le O(n \log^2 n / 2^b)$

5장과 종합하면 고정된 $b$ 에 대해서 시간 복잡도는 expected $O(n^2 \log^3 n / 2^{2b})$ 이다. 한편, 주어진 쿼리가 해당 $b$ 를 얻을 확률은 최대 $O(2^{2b} / n^2)$ 이다. 모든 $b$ 에 대해 합하면 $O(\log^4 n)$ 으로 계산된다.