그래프의 간선 색칠 문제

이 글은 https://codeforces.com/blog/entry/75431 의 한글 번역본입니다. 가능하면 원문을 보는 것을 추천합니다 ;) 

그래프 $G$가 주어질 때, 각 정점 $v$에 대해 자연수 색상 을 배정하여 간선으로 직접 연결된 정점 쌍마다 다른 색상을 배정해야 한다. 이 때, 배정된 최대 색상을 최소화해보자. 즉, 서로 다른 색의 수를 최소화해야 한다.

이 문제는 그래프의 정점 색칠 (Graph Coloring, Vertex Coloring) 문제로, NP-complete임이 잘 알려져 있다. 너무 어려우니까 다른 문제를 생각해 보자.

그래프 $G$가 주어질 때, 각 간선 $v$에 대해 자연수 색상 을 배정하여 간선으로 직접 연결된 정점 쌍마다 다른 색상을 배정해야 한다. 이 때, 배정된 최대 색상을 최소화해보자. 즉, 서로 다른 색의 수를 최소화해야 한다.

이 문제는 그래프의 간선 색칠 (Edge Coloring) 문제로 알려져 있다. 비슷한 말로, Line graph의 정점 색칠 문제라고 부를 수도 있다. 이번 글에서는 간선 채색 문제에 대한 효율적인 알고리즘을 다룬다.

일반 그래프

그래프의 최대 차수를 $D = max_{v \in V(G)}deg(v)$ 라고 하자. 한 정점에 인접한 간선들은 모두 다른 색을 가져야 하기 때문에, 모든 간선을 색칠하는 데는 최소 $D$ 개의 색이 필요하다.

그래서 만약 우리가 어떻게든 간선에 $D$개의 색상을 칠하는 알고리즘을 찾는다면, 이것은 간선 색칠 문제 전체를 해결하는 알고리즘이 된다! 하지만 아쉽게도 이것은 불가능하다. 정점이 3개가 있는 사이클에서는, $D = 2$ 를 만족하지만, 간선을 색칠하는 데 최소 3개의 색이 필요하다.

다행이도, Vizing은 이것이 거의 사실 임을 보였다.

Theorem. (Vizing, 1964년). 모든 단순 그래프는 $D+1$ 개의 색으로 간선을 색칠할 수 있다.

Proof: 이 글에서는 생략한다. 관심있는 독자는 여기를 참고하라.

이 때:

• 그래프가 동일한 정점을 연결하는 여러 간선을 가진 경우 (중복 간선) 정리가 유지되지 않는다.
• 그래프를 $D$ 색상으로 색칠할 수 있는지 판별하는 것은 NP-hard이다. 고로 간선 색칠 문제는 여전히 NP-hard 이다.

Vizing Theorem을 통해서 $D+1$ 개의 색으로 간선을 칠할 수 있을 뿐만 아니라, $D+1$ 개 이하의 색으로 간선을 칠하는 $O(nm)$ 알고리즘 역시 존재한다. 이 알고리즘의 구현은 여기서 찾을 수 있다. ACM-ICPC Daejeon Regional 2014 A번 문제 는 정확히 이 알고리즘을 구현하는 문제이고, 또한 이 알고리즘의 구현이 팀노트에 있다면 특정 문제들을 굉장히 간단하게 해결할 수도 있다. 예를 들어, NCPC 2018 G번 문제 는 수학적으로 어려운 풀이를 요구하지만, 위 $O(nm)$ 알고리즘을 적용하면 아주 간단하게 해결할 수 있다.

Vizing Theorem과, 이를 구현하는 효율적인 $O(nm)$ 알고리즘은 모두 상당히 복잡하며, 이 글에서는 이러한 알고리즘의 존재만 다룰 것이다. 이제 이야기를 돌려서 특수한 그래프인 이분 그래프 에서 이 문제를 효율적으로 해결하는 방법을 논의해 보자.

이분 그래프

최적의 간선 색칠을 찾으려면 간선이 $D$ 개의 색으로 색칠될 수 있다는 것을 증명해야 한다. 일반적인 그래프에서 이것은 참이 아니지만, 어쨌든 3-cycle은 이분 그래프가 아니고, 짝수 길이 사이클에서는 전부 2개의 색으로 색칠이 가능하니, 혹시 이분 그래프에서는 사실일 수도 있지 않을까?

• Theorem. 모든 이분 그래프에 대해 간선을 $D$ 개의 색으로 색칠할 수 있다.
• Proof. $D$ 에 대한 귀납법을 사용한다.
  • $D = 0$ 이면 자명하다.
  • 그렇지 않으면, 먼저 그래프의 왼쪽/오른쪽 부분의 정점 개수가 같도록 더미 정점을 추가해 준다. 그리고, 모든 노드가 차수 $D$를 가지게 하기 위해, 왼쪽 / 오른쪽에서 각각 차수가 $D$ 미만인 아무 정점을 잡아서 반복적으로 이어주자. 그래프가 이분 그래프이니, 왼쪽/오른쪽 부분에 있는 정점들의 차수 합은 동일하고, 고로 계속 추가해줘서 모든 차수가 $D$가 되도록 바꿔줄 수 있다.
  • 이제, 이 그래프에 완벽 매칭이 있음을 증명한다. 그래프에 왼쪽/오른쪽 부분을 $L, R$ 이라 하자. 임의의 $S \subseteq L$ 에 대해, 이 정점에 인접한 정점 집합을 $N(S)$ 라고 하자. $S$ 의 차수 합은 $D|S|$ 이다. $N(S)$ 의 차수 합은 $D|N(S)|$ 이다. $S$ 에 인접한 간선들은 모두 $N(S)$ 의 차수에 기여하니 $D|S| \leq D|N(S)|$ 이다. $D > 0$ 이니 $|S| \le |N(S)|$ 가 만족되고 홀의 정리에 의해 완벽 매칭을 찾을 수 있다.
  • 이제, 완벽 매칭과 완벽 매칭이 아닌 간선을 분리하면, 완벽 매칭은 1개의 색으로 칠할 수 있고, 그 밖에 속하는 간선들의 최대 차수는 $D-1$ 이하이다. 더미 간선을 모두 제거하자. 그 후에도 완벽 매칭은 1개의 색으로 칠할 수 있고, 그 밖에 속하는 간선들의 최대 차수는 $D-1$ 이하이다. 고로 귀납 가정에 의해 $D-1$ 이하의 간선들을 색칠할 수 있고, 그 이후 완벽 매칭을 $D$ 로 칠하면 된다.
• Remark. 다중 간선이 있어도 정리는 성립한다.

이 증명을 통해서, 이분 그래프의 간선 색칠을 찾는 알고리즘을 얻을 수 있다. 위 Theorem과 같이 번거롭게 간선을 추가할 필요는 없고, 모든 노드에 대해 차수가 $D$ 인 정점을 전부 커버하는 매칭만 찾으면 되기 때문이다. 그것만으로도 귀납법을 사용하기 충분하고, 위 증명은 그러한 매칭의 존재성을 보장한다. 일반적인 이분 매칭에서, 특정 정점을 무조건 포함하는 매칭을 찾는 문제인데, 해당 정점을 잇는 간선의 용량을 1로 강제하면 되니 L-R Maximum Flow 를 사용하면 된다. Dinic's algorithm을 사용하면, $O(D \times MN^{0.5})$ 시간에 색칠을 찾을 수 있다. 따라서 이분 그래프의 간선 색칠은 다항 시간에 해결할 수 있다.

실제로는 위에 적힌 알고리즘처럼 Maximum flow를 사용하지 않으면서 짧은 코드로 간선 색칠을 찾는 $O(NM)$ 알고리즘이 존재한다. 이 알고리즘에 대해서는 이 링크에서 설명되어 있고, 구현은 이 링크에서 찾을 수 있다.

더 빠르게

더 빨리 할 수 있을까? 다시 $O(D \times MN^{0.5})$ 알고리즘으로 돌아가자. 시간 복잡도를 $O(D \times MN^{0.5})$에서 $O(MN^{0.5} \log D)$로 줄이는 간단하면서도 아름다운 아이디어를 소개한다.

이 아이디어는, $\log$ 에서 추측할 수 있듯이, 분할 정복이다. $D$ 가 홀수일 경우, 위와 같이 단순히 최대 차수를 $D-1$로 줄여주자. $D$가 짝수일 경우 그래프를 최대 차수가 $\frac{D}{2}$인 두 조각으로 분할해 보자. 과연 가능은 할까?

짝수 차수 그래프에 대한 다음과 같은 잘 알려진 사실을 기억해보자.

오일러 회로 (Euler Circuit). 모든 정점의 차수가 짝수인 연결된 그래프의 경우, 모든 간선을 정확히 한 번 방문하는 회로(circuit)가 있다. 또한 선형 시간에 오일러 회로를 계산하는 알고리즘이 존재한다.

이제, 홀수 차수 정점들을 서로 연결시키기 위해 더미 간선들을 추가하자. 홀수 차수 정점은 짝수개 존재하니, 이들을 (1, 2), (3, 4) 와 같이 임의로 매칭해 줘도 문제가 없다. 이제, 각 연결 컴포넌트에서 선형 시간에 오일러 회로를 구하자.

오일러 회로는 이분 그래프에서 짝수 길이를 갖고 있다. 한 컴포넌트에 대한 오일러 회로를 $C = {e_1, e_2, \ldots, e_{2k}}$로 표시하자. 홀수 번호의 간선 ($e_1, e_3, e_5 \ldots$) 은 파란색으로, 짝수 번호의 간선은 빨간색으로 색칠하자. 그러면 각 꼭지점 $v$에 대해 $\frac{deg(v)}{2}$ 파란색 노드와 $\frac{deg(v)}{2}$ 빨간색 노드에 인접해 있음을 알 수 있다! 회로가 특정 색으로 정점에 들어가면 반대쪽 색으로 정점을 나가게 되기 때문이다.

따라서 각 연결 컴포넌트에 대해 오일러 회로를 계산하고, 간선을 파란색과 빨간색 세트로 나누자. 더미 모서리를 제거하면 각 색상에 대해 최대 차수가 $\frac{D}{2}$ 인 분할을 찾을 수 있다. 고로 두 세트를 재귀적으로 색칠해 주면 된다. 모든 간선은 최대 $O(\log D)$ 재귀 단계에서 고려되기 때문에, 각 단계는 최대 $O(N^{0.5})$ 만큼의 계산을 각각 요구하니, 시간 복잡도는 $O(MN^{0.5} \log D)$이다.

엄청나게 빠르게

이제 이 문제를 $O(M\log M \log D)$ 에 해결하는 알고리즘을 소개한다. 이 알고리즘은 플로우를 전혀 사용하지 않으며, 선형에 준하는 매우 효율적인 복잡도를 가진다.

맨 처음의 증명으로 돌아가서, 그래프의 모든 차수가 같다고 가정하자. 맨 처음의 증명처럼 간선을 추가하면 추가한 간선이 거의 $O(N^2)$ 개가 되어 비효율적이다.

한편, 차수가 작은 노드들을 합쳐주는 전략을 사용해 보자. 이분 그래프의 같은 쪽에 속하는 두 노드는, 두 노드를 합쳐준 후 색칠을 구해줄 수 있다. 나중에 두 노드가 분할된다고 하더라도, 색칠이 깨지지 않기 때문이다. 따라서 이분 그래프의 왼쪽/오른쪽 정점 집합에 대해 $deg(v) \le \frac{D}{2}$을(를) 가진 노드가 2개 이상이라면 두 노드를 합치는 것을 반복하자. 이 절차가 끝나면 $deg(v) \le \frac{D}{2}$를 만족하는 노드가 왼쪽/오른쪽에 최대 1개, 고로 2개 이하이다. 이제, 맨 위 증명과 같이 더미 노드를 추가하는 식으로 에지를 더해도, $O(M)$ 개의 간선이 추가된다. 모든 정점이 $deg(v) \geq \frac{D}{2}$ 를 만족하면, 간선을 위와 같이 더해줘도 크기가 최대 2배가 되기 때문이다.

이제 그래프의 모든 차수가 같다고 가정하자. 흥미롭게도, 2010년에 발견된 다음 논문에 의하면, 모든 차수가 같은 이분 그래프에서는 $O(M + N \log N)$ 에 완벽 매칭을 계산하는 간단한 랜덤 알고리즘이 존재한다.

개략적으로 논문의 내용을 요약하자면, 논문의 알고리즘은 사실 네트워크 플로우를 사용하여 완벽 매칭을 찾는 방법과 크게 다르지 않다. 소스와 싱크를 가진 일반적인 flow graph를 만들고 augmenting path를 찾는 전략을 상기해보자. 이 논문에는두 가지 주목할 만한 차이점이 있다.

• 간선이 현재 매칭에 있다면, 역변을 만들지 말고 두 정점을 한 정점으로 합쳐주자. 이렇게 하더라도 상황이 크게 달라지지 않는다 (실제 구현에서 두 정점을 명시적으로 합칠 필요도 없다).
• DFS로 경로를 찾지 않고, random walk를 사용한다. 어떠한 정점에 있을 때, 나갈 수 있는 모든 정점 중 하나를 랜덤하게 골라서, 싱크에 도달할 때까지 반복한다.

직관적으로, 두 번째 차이점은 augmenting path가 짧은 초기 단계에서 매우 빠르게 실행될 것이다. 예를 들어, 첫 번째 augmenting path를 찾을 때 경로의 길이는 무조건 3이 되고, 꽤 높은 확률로 이것이 오랫동안 (대략, 매칭을 한 반 정도 찾을 때까지) 유지될 것이다. 시간 복잡도가 단순히 찾은 경로의 길이에 비례하기 때문이다. 이제 논문에서는 다음과 같은 내용을 주장한다. 그 증명은 꽤 복잡하니 생략한다.

Lemma 6 (논문 기준). 현재 그래프에서 $m < n$ 개의 매칭을 찾은 경우, random walk에 의해 찾는 경로의 길이의 기댓값은 $2 + \frac{n}{n - m}$이다.

모든 $0 \le m \le n - 1$에 대해 이를 반복 하면, $2n + n \sum_{i=1}^{n}\frac{1}{i} = O(n \log n)$ 이 된다. 고로 완벽 매칭을 $O(N \log N)$ 에 찾을 수 있다.

연습 문제

이 주제에 대한 연습 문제들을 나열한다. 몇 개의 문제들은 위 글과 직접적인 관련이 있고, 몇 개의 문제들은 여러 다른 종류의 문제들을 간선 색칠 문제로 환원하는 창의성을 요구하는 문제이다.

• Codeforces: Edge coloring of Bipartite graphs
• AGC 037 D. Sorting a Grid
• OpenCup 2019/2020 GP of Wroclaw G: Choreography
• Codeforces: Privatization
• Codeforces: Football
• COCI 2018/2019 Round 1 #5. Teoreticar