※ 이 공부기록은 부정확한 내용이 다수 포함되어있을 수 있다. 또한 이 글은 정보 전달이 주 목적이 아닌 개인적인 기록용이어서 체계적으로 내용이 정리되어 있지 않을 수 있다. 읽는이의 양해를 바란다.
개요
PS/CP에서 주어지는 그래프 중 정점이 많이 주어지는(10만개 이상) 그래프는 대부분 sparse하다는 점을 의식해본 적이 있을 것이다. 시간 제한 내로 그래프가 dense해질 정도로 에지를 입력을 통해 많이 줄 수 없기 때문이다. 그렇다면 이 sparse하다는 점을 파고드는 문제해결전략도 있을 것이라는 생각이 이어서 든다.
이 글에서는 그래프의 밀도와 관련된 지표 중 하나인 deneneracy를 설명한다. 그리고 이와 관련된 degeneracy ordering을 소개하고, PS에서 이를 활용하는 해결할 수 있는 대표적인 문제인 counting 3-cycle과 counting 4-cycle 문제를 살펴본다.
이 내용을 이해한다고 바로 PS/CP 실력이 증가하거나 하지는 않겠지만, 이후에 그래프 관련 개념을 공부하거나 문제를 풀 때 조금 더 넓은 시야를 가지고 접근하는 등 도움이 될 것이라고 생각한다.
Degeneracy, \(k\)-core
\(G\)의 모든 subgraph의 "degree가 가장 작은 정점"의 degree가 \(k\) 이하일 때 \(G\)를 \(k\)-degenarate graph라 한다.
또한, 그래프 \(G\)가 주어질 때, \(G\)의 부분그래프 중 "degree가 가장 작은 정점"의 degree가 가장 큰 부분그래프가 존재할 것이다. 그러한 부분그래프의 크기를 \(G\)의 degeneracy라고 정의한다. 즉, \(G\)의 degeneracy는 \(G\)가 \(k\)-degenerate graph가 되게 하는 \(k\)의 최솟값이다. 또한 degree가 가장 작은 정점의 degree가 \(k\)인 \(G\)의 maximal한 connected subgraph들을 각각 \(k\)-core이라고 부른다.
degeneracy는 주어진 그래프에서 모든 정점의 degree가 degeneracy \(k\)이상인 부분(\(k\)-core)이 그래프에 있다는 것을 보여주는 값이므로, 이를 통해 그래프의 부분밀도에 대한 정보를 간접적으로 알 수 있다.
※주의: 당연하지만, \(k\)-core의 형태가 complete graph일 필요는 없다. complete graph의 형태가 아닌 \(k\)-core의 가능한 형태 중 하나로 regular graph가 있다.
한편, 어떤 그래프의 간선의 개수가 \(E\)라면 이 그래프의 degeneracy는 \(O(\sqrt{E})\)이 됨을 관찰하자. degeneracy가 \(k\)인 그래프는 정점이 \(k+1\)개인 complete graph이므로 \(\frac{k(k+1)}{2}\)개의 간선이 필요하기 때문이다.
Degeneracy Ordering, Coloring Number
※여기서 말하는 coloring number은 chromatic number과 다른 개념이므로 유의하자.
그래프의 degeneracy를 계산하는 것은 어렵지 않다. 가장 degree가 작은 정점을 지우는 것을 반복하면서, 매 순간의 최소 degree 정점의 degree 중 최댓값을 구하는 찾으면 된다. 이해와 증명 모두 직관적이므로 자세한 설명은 생략한다. 이 과정에서 지워지는 정점의 순서를 degeneracy ordering이라고 한다.
degeneracy ordering의 특징은 각 정점에 대하여 이후에 등장하는 정점의 수가 전체 그래프의 degeneracy \(k\) 이하라는 것이다.
degeneracy ordering의 역순으로 각 정점을 지금까지 색칠된 인접 정점을 칠하는 데에 사용되지 않은 색을 칠해나가는 전략을 생각해보자. degeneracy ordering의 특징을 잘 생각해보면 색칠할 차례의 각 정점에 대하여 그보다 앞 순서에서 색칠된 인접한 정점의 개수는 많아야 \(k\)개이므로 많아야 \(k+1\)개의 색으로 인접한 정점의 색이 다르게 그래프의 정점을 색칠할 수 있음을 알 수 있다. 이러한 이유에서 \(k+1\)을 coloring number라고 부르기도 한다. 다만 이름이 chromatic number(인접한 정점의 색이 다르게 그래프의 정점을 칠하기 위해 필요한 색의 최소 개수)와 혼동되기 쉬우므로 이 이름으로 자주 부르지는 않는다.
Counting 3-cycles
이제 degeneracy ordering을 활용하여 해결할 수 있는 문제인 counting 3-cycles를 소개한다. counting 3-cycles 문제는 다음과 같은 문제를 말한다.
정점이 \(V\)개이고 간선이 \(E\)개(self-loop, duplicate edge 없음)인 무방향그래프 \(G\)가 있다. 이 그래프에서 찾을 수 있는 3-cycle(세 개의 정점으로 구성된 cycle)은 총 몇 개인가?
\(N\) 또는 \(E\)가 10만 이상인 그래프가 입력으로 주어지면 위 문제를 간단한 방법으로 해결하기는 쉽지 않아보인다. 그러나 문제의 형태가 매우 단순하다 보니 다양한 풀이가 존재하는 문제이기도 하다. 이 글에서는 degeneracy ordering을 이용한 방법을 알아보자.
주어진 그래프가 DAG가 되게끔 각 간선에 방향을 임의로 부여해보자. 이 때, 원래 그래프에서의 3-cycle은 항상 (cycle 위에서) indegree가 2인 정점 \(A\), indegree와 outdegree가 각각 1인 정점 \(B\), outdegree가 2인 정점 \(C\)로 구성된다.
그렇다면, 주어진 그래프의 모든 간선에 대하여 그 간선의 양 끝 정점과 (DAG에서) 인접한 정점을 찾는 것을 반복하는 것으로 각 cycle을 \(A\)와 \(B\)를 잇는 간선이 선택되었을 때 정확히 한 번 셀 수 있다.
이제, DAG를 degeneracy ordering을 활용하여 구성해보자. 각 간선의 방향을 degeneracy ordering 기준 먼저 오는 정점에서 나중에 오는 정점으로 향하게 설정하면, 각 정점의 outdegree는 그래프의 degeneracy \(k\) 이하가 된다. 또한 설명했듯이 \(k\)는 \(O(\sqrt{M})\)이다.
따라서 위에서 구성한 알고리즘은 degeneracy ordering을 활용하여 구성한 DAG에서 각 간선 선택의 경우의 수 \(E\)에 대하여 두 정점과 인접한 공통 정점집합 찾기를 각각 \(O(\sqrt{M})\)에 해낼 수 있다.
따라서 degeneracy ordering을 활용하면 counting 3-cycle 문제를 \(O(M\sqrt{M})\)에 해결할 수 있다.
Counting 4-cycles
3-cycle의 경우와 비슷한 방법으로 counting 4-cycles 문제도 정의 및 해결할 수 있다. counting 4-cycles 문제는 다음과 같은 문제를 말한다.
정점이 \(V\)개이고 간선이 \(E\)개(self-loop, duplicate edge 없음)인 무방향그래프 \(G\)가 있다. 이 그래프에서 찾을 수 있는 4-cycle(네 개의 정점으로 구성된 cycle. 구성 간선의 집합이 다르면 다른 cycle이다.)은 총 몇 개인가?
3-cycle의 경우와 다르게, 4-cycle은 DAG 위에서도 다양한 형태로 나타날 수 있다. 특히, (원래 그래프에서의) 4-cycle은 (DAG에서의) indegree가 2인 정점의 개수가 1개일 수도 있고 2개일 수도 있다. 그러니 각 4-cycle을 한 번씩만 세려면 조금 더 구체적인 조건을 세워야 할 것이다.
이러한 조건을 세우는 방법 중 하나로 indegree가 2이면서 맞은편에 있는 정점의 degeneracy order보다 큰 order를 가지는 정점을 갖는 4-cycle만을 세는 것이 있다.
이러한 4-cycle은 그래프의 각 정점(이것이 indegree가 2인 찾고자 하는 정점의 맞은편 정점이다)으로부터 "원래 그래프에서의" 인접 정점을 찾고, 그 정점에서 이어서 DAG에서의 degeneracy order가 첫 정점보다 더 큰 인접 정점(이것이 indegree가 2인 찾고자하는 정점이다)들을 조사하는 것으로 모두 셀 수 있다.
위 알고리즘에서, 무방향그래프에서의 인접 정점을 찾는 횟수는 \(O(M)\)이며 각 정점에서 인접 정점을 조사하는 과정은 \(O(\sqrt{M})\)이다. 따라서 이 알고리즘의 최종 시간복잡도는 \(O(M\sqrt{M})\)이 된다.
여담
이 글에서 소개한 내용 말고도, degeneracy ordering은 그래프의 모든 maximal clique를 효율적으로 탐색하는 알고리즘인 Bron-Kerbosch 알고리즘의 최적화에 쓰이는 등 다른 곳에서도 사용하는 개념이다. 언젠가 clique 관련된 글을 작성하게 된다면 같이 소개하지 않을까....
3-cycle과 4-cycle을 셀 때, degeneracy ordering이 아닌 다른 ordering을 이용하기도 한다. PS/CP에서 널리 쓰이는 ordering 중 하나로 각 정점들을 degree가 \(\sqrt{M}\) 이상인 정점과 미만인 정점으로 나누어 degree가 낮은 정점들에 낮은 order를 부여하고 degree가 높은 정점에 높은 order를 부여하는 방법이 있다. degree가 낮은 정점의 outdegree는 많아야 \(\sqrt{M}\)이 되며, degree가 높은 정점은 그래프에 많아야 \(O(\sqrt{M})\)개이므로 degree가 높은 정점의 outdegree 또한 많아야 \(\sqrt{M}\)이 됨을 관찰하자.
특정 형태의 그래프의 개수를 세는 문제를 해결할 때, bitset을 활용한 최적화를 시도하는 것도 좋은 방법이 될 수 있다.
관련 문제
degeneracy ordering을 이용한 정점 채색법을 활용해보자.
이 글의 흐름에서는 살짝 벗어나지만, 이 문제와 관련된 더 많은 내용을 알고 싶다면 Brooks' Theorem과 Δ-coloring을 찾아보자.
planar graph의 degeneracy는 5 이하임을 증명하고, 이를 활용해 문제를 해결해보자.
위 degeneracy의 상한을 이용하면 \(O(M\sqrt{M})\)으로 풀리지 않을 정도로 \(M\)이 커져도 충분히 문제를 해결할 수 있음을 알 수 있다.
DAG에서의 세 정점이 이룰 수 있는 관계를 잘 생각해보자.
4-cycle을 세는 기본 문제이다.
4-cycle에 뭔가가 더 붙은 그래프도 세어보자.
비슷한 방법으로 4-clique 또한 셀 수 있다.
[BOJ31185] Ancient Magic Circle in Teyvat
포제원리를 활용하면 4-anticlique 또한 셀 수 있다.
참고 자료
https://en.wikipedia.org/wiki/Degeneracy_(graph_theory)
https://dl.acm.org/doi/10.1145/2402.322385
https://www.cs.cornell.edu/courses/cs6241/2019sp/readings/Chiba-1985-arboricity.pdf : 그래프의 밀도와 관련된 또다른 지표인 arboricity의 개념을 이용하여 3-cycle 및 4-cycle counting을 계산하는 방법을 소개한다. arboricity와 degereracy는 많아야 2배 차이나는 지표이므로, 전반적인 흐름은 degeneracy를 활용한 것과 크게 다르지 않다.