티스토리 뷰

공부

Directed MST in subquadratic time

구사과 2020. 12. 17. 21:20

최소 스패닝 트리 (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하면 됩니다.

'공부' 카테고리의 다른 글

2021.01.17 problem solving  (0) 2021.01.17
2020.12.24 problem solving  (7) 2020.12.24
Directed MST in subquadratic time  (0) 2020.12.17
2020.12.06 problem solving  (1) 2020.12.06
2020 ICPC Seoul Regional  (0) 2020.11.16
2020 ICPC 서울 인터넷 예선  (4) 2020.10.10
댓글
댓글쓰기 폼
공지사항
Total
561,794
Today
521
Yesterday
355