ARC099 E Independence & 재밌는 완전그래프 문제들

처음으로 AC를 받은 ARC E번!

ARC099E. Independence

Independence는 PS에서 흔치 않게 완전그래프가 등장하는 문제다.

하나만 포스팅하기 아까워서, 역시 완전그래프가 등장하는 POI문제 2개를 추가로 포스팅하기로 했다. 세 문제의 관찰이 모두 다르다.

POI11. Party

POI11. Conspiracy

여담이지만 Party는 Stage 3-2고 Conspiracy는 Stage 1-1데 Conspiracy가 훨씬 어렵다. 도대체 그들의 스테이지 선정 기준은...

---

---

Intro) POI11. Party

Tag : Complete graph, Naive(...)

크기 \(n\) (3의 배수)인 그래프가 주어지는데, 최소한 \(\frac{2}{3}n\) 크기의 clique가 있다는 것이 보장된다. 여기서 크기가 \(\frac{n}{3}\) 이상인 clique를 뽑아내야 한다.

놀랍게도 이 문제는 그냥 하면 된다. 크기 \(\frac{2}{3}n\)짜리 clique에 속한 정점들을 '인싸', 그렇지 못한 멤버들을 '아싸'라고 해보자.

이제 그래프를 돌면서, 연결되어 있지 않은 두 정점이 있다면 그 두 정점을 바로 그래프에서 제거하면 된다.

제거하는 정점은 무조건 (인싸, 아싸)거나 (아싸, 아싸)인데, 아싸는 최대 \(\frac{n}{3}\)명이므로 이 procedure에서 부작용으로 제거되는 인싸의 수는 많아야 \(\frac{n}{3}\)명. 따라서 최소한 \(\frac{n}{3}\)명의 인싸가 살아남게 된다.

---

Main) ARC099E. Independence

Tag : Complete graph, Inverse graph, DP

크기 \(n\)인 그래프의 정점을 두 집합으로 분할하는데, 두 induced subgraph는 모두 clique이어야 한다.

그 분할이 가능한지 판별하고, 가능하다면 두 clique의 크기를 최대한 비슷하게 만들어야 한다.

tmi) 사실 나는 이 문제가 뒤의 Conspiracy와 매우 흡사하다고 생각했고, 그래서 (Conspiracy의 핵심 idea를 이해하지 못한 채로) 비슷한 접근법을 사용하다가 사풀로 빠져들고 말았다. ㅂㄷㅂㄷ

사실 완전그래프를 주면 내 경우 가장 자연스럽게 생각나는 게 Complement graph인데, 그런 면에서는 가장 '자연스러운' 완전그래프 문제라고 할 수 있겠다.

주어진 그래프의 Complement graph를 생각하자. 그렇다면 문제가 요구하는 바는 그래프가 이분그래프인지 판별하는 것이다! 즉, 모든 정점에 R / B의 2가지 색을 칠하여 인접한 두 정점이 다른 색을 갖도록 하는 문제이다.

이 때, 이분그래프의 Connected Component별로 (모든 정점의 색을 반전시킨 것을 제외하고) 유일하게 색칠 방법을 결정할 수 있다. 이제 \(O(n^2)\) DP를 통해 컴포넌트별로 어떤 방법을 사용할지를 결정해주면 된다.

---

Outro) POI11. Conspiracy

Tag : Complete Graph, Degree

내가 아는 PS문제 중 가장 멋진 관찰이 들어간 문제로 꼽는다. 최근에 풀어본 것 중에는 이거랑 동굴 탐험이 best.

Independence와 마찬가지로 정점을 두 집합으로 분할하되, 한쪽은 Clique, 다른 한쪽은 Inverse Complete graph (E = 0인 그래프)이어야 한다.

두 집합은 모두 nonempty여야 할 때, 가능한 분할의 수를 구해야 한다.

Clique인 쪽의 크기를 \(k\)로 고정하고, 그 정점을 \(v_1, v_2, \ldots v_k\)라고 하자.

이 때 에지의 수를 이용한 더블카운팅을 하면 다음이 성립함을 알 수 있다!

$$ \sum_{i=1}^{k} \deg (v_{i}) = E + {}_{k}C_{2} $$

모든 에지는 (Clique 내부 에지) + (Clique - Non Clique 사이의 에지)밖에 없다는 점을 생각하면 이 관찰을 이해할 수 있다.

그리고 만약 Clique에 속한 어떤 정점 \(v\)보다 차수가 더 큰 정점 \(w\)가 Non-Clique에 있다면 Clique에서 \(v\)를 빼고 \(w\)를 넣어야 함을 알 수 있다. Non-Clique에도 \(w\)와 연결된 점이 있기 때문.

따라서 이 문제는 결국 차수가 가장 큰 정점 \(k\)개에 대해서 다음 식을 만족시키는 경우의 수를 세는 문제로 바뀐다!

$$ \sum_{i=1}^{k} \deg (v_{i}) = E + {}_{k}C_{2} $$

유일하게 가능한 중첩은 차수가 같은 정점들끼리 Clique와 Non-Clique을 왔다갔다 하는 경우뿐이다. 이 경우의 수(중첩도)는 차수가 \(d\)인 정점의 개수를 미리 세 놓고 Combination을 이용해 구할 수 있다. 복잡도는 입력 제외 \(O(n \lg n)\)이다. 빛빛빛...

이걸 그냥 돌리면 그래프가 \(K_n\)이거나 \(\bar{K_n}\)인 경우 한쪽이 empty-set이 되는 예외가 생긴다. 이는 반복문을 \(1\ldots n\)이 아니라 \(1\ldots n-1\)까지 돌려서 clique의 크기를 제한함으로써 쉽게 처리할 수 있다.