Directed MST in subquadratic time

최소 스패닝 트리 (MST) 는 무방향 그래프에서만 정의되는데, 방향 그래프에서도 MST 비슷한 것을 정의하기도 합니다. Minimum Arborescence 이라고도 부르는데, 방향 그래프 $G$ 와 루트 정점 $r$이 주어졌을 때

• 무방향 그래프로 봤을 때 사이클이 없고
• $r$ 에서 모든 정점을 도달 가능하면

이를 $r$ 을 루트로 한 Directed MST라고 합니다. 루트 정점을 무조건 정의해 줘야 함에 주의해야합니다.

이 글에서는 Chu–Liu/Edmonds' algorithm 이라고 불리는, Directed MST를 구하는 알고리즘을 간단히 소개합니다. 일반적으로 $O(VE)$ 시간 복잡도에 해결하는 방법을 사용하는데, 여기서는 $O((V + E) \log E)$ 에 문제를 해결할 것입니다.

다음과 같은 세 가지 사실을 소개합니다.

• Fact 1. Directed MST는 다음 두 조건을 만족하는 최소 가중치 간선 부분집합이다:

  • 무방향 그래프로 봤을 때 사이클이 없다.
  • 루트 $r$ 를 제외한 모든 정점에 대해서 indegree가 정확히 1이다.

  Remark on Fact 1. 두 성질이 Matroid axiom을 만족하기 때문에, 그냥 matroid intersection을 사용해 버리면 $O(NM^2)$ 에 문제를 해결할 수 있습니다. 일종의 naive algorithm에 속합니다.

• Fact 2. 루트가 아닌 모든 정점에 대해서, 해당 정점으로 들어오는 최소 가중치 간선을 $e(v)$ 라고 하고, 그 가중치를 $w(e(v))$ 라고 하자. Directed MST의 가중치 합은 최소 $\sum w(e(v))$ 이다. (Fact 1에 의해 자명)

• Fact 3. $e(v)$ 들을 모아서 그래프를 만들자. 만약 이 그래프에 사이클 $C$ 가 존재한다면, 어떠한 Directed MST $T$ 가 존재하여, $|C \cap T| = |C| - 1$ 이다.

  • Proof. $|C \cap T| = |C|$ 일 수는 없으니 $|C \cap T| \geq |C| - 1$ 임을 보이는 것으로 충분하다. $C$ 에서 루트와 거리가 최소인 점을 $v_1$ 이라고 하고, 거기서부터 순서대로 $v_1, v_2, \ldots, v_k$ 와 같이 정점들을 나열하자. 만약 모든 $1 \le i < k$ 에 대해서 $(v_i, v_{i + 1})$ 을 잇는 간선이 존재한다면 증명이 종료된다. 그렇지 않은 최소 인덱스의 정점을 $v_i$ 라고 하자. $v_{i + 1}$ 의 부모를 $v_i$ 로 바꿔줘도 indegree는 1이며 가중치가 늘어나지 않는다. 이제 무방향 그래프로 봤을 때 사이클만 없으면 증명이 된다. 이는 $v_{i + 1}$ 과 원래 부모를 끊어도, $v_i$ 가 루트에서 도달 가능함을 보이면 되는데, $v_i$ 에서 루트로 가는 경로는 $C$와 무관한 정점을 거치다가 $v_1, v_2, \ldots, v_i$ 를 순서대로 타고 돌아온다. $v_1$ 이 루트와 가장 가깝기 때문에 이 성질이 성립하며, 이 경로 중 $v_{i + 1}$ 은 등장하지 않으니 그 정점의 부모가 바뀌는 것은 $v_i$ 의 경로와 무관하다. 이를 모든 사이클에 대해 반복하면 원하는 Directed MST를 찾을 수 있다.

Fact 2, 3을 조합하면 Directed MST를 만드는 과정을 상상해 볼 수 있습니다. 루트가 아닌 모든 정점에 대해서 최소 가중치 간선을 고릅시다. 만약 이 간선들이 트리를 만든다면 그 즉시 Directed MST를 찾은 것입니다. 아니면 크기 2 이상의 사이클을 찾았는데, 여기서 최소 한 개 이상의 간선이 MST에 속했다는 사실을 알 수 있습니다. 고로 이 정보를 적절히 추가해서 MST에 대한 정보를 키워나가면 됩니다.

이제 사이클을 찾았다는 정보를 어떻게 활용하는지 알아봅시다. 이 부분에서는 굉장히 흥미로운 방법으로 입력의 크기를 줄입니다. 사이클을 하나의 노드로 contract해 주고, 생기는 모든 루프를 제거해 줍니다. 사이클로 들어오는 간선을 하나 골랐다는 것은, 해당 간선을 통해서 루트에서 사이클에 접근하게 될 것이며, 해당 간선과 끝점을 공유하는 사이클 상의 간선을 사용하지 않을 것이라는 뜻입니다. 사이클을 하나의 노드로 contract할 때, 해당 사이클에 있는 모든 간선들을 고른 후, 사이클로 들어오는 간선 $e = u \rightarrow v$ 에 대해, $w(e) := w(e) - w(C_v)$ 로 설정합니다. 이 때 $C_v$ 는 사이클 상에서 $v$ 로 들어오는 간선입니다. 즉 $e$ 를 고르는 것에 $v$ 로 가는 간선을 취소해 준다는 정보를 추가하는 것입니다.

이렇게 하면 항상 정점 수를 1 줄이거나 종료하기 때문에, $O(NM) = O(N^3)$ 시간에 Directed MST를 찾을 수 있습니다.

이 알고리즘을 최적화하는 방법은 다음과 같습니다. 먼저 각 스텝마다 해당 정점으로 들어오는 최소 가중치 간선을 일일이 찾아 줄 필요가 없으며, contract가 일어날 때마다 그때 그때 필요한 간선들만 업데이트해 주면 됩니다. 또한, 그래프에서 사이클이 있는지, 그리고 하나의 노드로 contract하는 연산들은 모두 Union-find를 사용해서 잘 관리할 수 있습니다.

이제 각 iteration을 따로 생각하지 않고, 큐에 $r$ 을 제외한 모든 정점들을 넣어주고 각 정점마다 순서대로 간선을 찾아줍시다. 또한 각 정점으로 들어오는 간선의 리스트는 Heap을 사용해서 관리합니다. 이제 큐가 비지 않을 때까지:

• 큐에서 정점 $v$ 를 뽑아 제거
• $e(v) : f(v) \rightarrow v$ 를 정답에 넣고 Heap에서 제거. 제거할 때 루프는 모두 무시하도록 구현 (contraction 정보를 가진 두번째 Union-find로 확인 가능)
• 사이클 확인을 위한 첫번째 Union-find에 $e(v)$ 를 추가함. 만약 사이클이 없다면, contract할 필요가 없음. 사이클이 있다면, 아래와 같은 contraction을 거침
  • $v, f(v), f(f(v)) \ldots$ 를 찾는 식으로 사이클 상의 모든 정점을 파악해 준 후, 이들을 두번째 Union-find (실제 contraction이 일어나는 곳) 에서 합쳐주고, 인접 리스트 역시 모두 하나의 힙으로 합쳐줌. 이 때 인접 리스트의 모든 원소에 Lazy하게 모든 값을 더해줘야 함 ($-w(C_v)$를 적용해야 하기 때문)
    • 인접 리스트는 Skew Heap, Randomized Meldable Heap 등을 구현하면 쉽게 amortized / worst-case $O(\log N)$ 에 합쳐줄 수 있음. Small-to-large를 사용해도 amortized $O(\log^2 N)$ 에 합쳐줄 수 있음.
  • 합쳐준 정점을 큐에 추가.

역추적이 상당히 까다로운데, 힌트는 다음과 같습니다. 일단 Union-find를 undo가 가능한 형태로 구현합시다 (한 번만 undo할 것이니 path compression이 좋다면 사용해도 무방합니다). 간선을 뽑는다는 것은, 해당 간선을 넣고 그 과정에서 다른 간선을 지웠다는 것입니다. 사이클을 생성할 때 새로운 노드를 만드는 식으로 구현합시다. 역추적을 할 때는 cycle을 합쳐준 과정을 역으로 봐주면서 이 더미 노드들을 "해체" 합니다. 이 과정에서 합치기 전에 있던 노드들 중 어떠한 노드의 간선을 "지워야 한다" 는 사실을 적어주는 것이 관건입니다. 고로 이 간선이 무엇인지 파악해야 하는데, 지워야 할 간선이 어느 사이클의 정점으로부터 왔었는지는, Union-find를 합친 시점으로 undo하면 알 수 있습니다. 이제 해당 위치에 적혀있는 간선에, 사이클로 들어온 $e(v)$ 를 overwrite하면 됩니다.