그래프에서 방송 지배

R&E를 하다가 알게된 건데 재밌음에도 한국에는 잘 알려져 있지 않은것 같아서 공유해보려고 합니다.

 

그래프에서 방송 지배는 대충

• 각 노드에 수가 부여돼있다.
• $0$ 초과의 수 $k$를 가진 노드는 자신과 거리가 $k$ 이하인 노드들을 지배한다.
• 어떤 노드가 적어도 하나의 노드에게는 지배당할 수 있도록 잘 설정해야 할 때 이 수들의 합을 최소화해야 한다.

이때 일반적인 그래프에서 재밌는 관찰을 몇 개 할 수 있다.

 

관찰 1: 하나의 노드는 하나의 노드에게만 지배당하는 최적해가 존재한다.

증명) 대충 두 노드가 같은 노드를 지배하면 같은 비용으로 더 큰 범위를 지배하는 그러한 해가 존재해서 이걸 계속 반복하면 된다.

 

이러면 어떤 노드가 지배하는 부분 그래프? 끼리 겹치지 않는다. 이 부분 그래프를 볼 이라고 부를 때 볼 내의 정점끼리 인접하면 그 볼끼리 인접하다고 볼 수도 있다. 따라서 이 볼만을 고려한 그래프도 생각 할 수 있고 이를 지배 그래프라 부르자.

또 하나의 재밌는 관찰을 할 수 있다.

 

관찰 2: 지배 그래프가 Path / Cycle이 되도록 하는 최적해가 존재한다.

증명) 지배 그래프에서 어떤 노드의 차수가 3 이상일 때 비용이 동일하고 더 적은 노드를 가지는 지배 그래프가 존재한다. (이것에 대한 증명은 케이스워크를 통해 할 수 있다.) 관찰 1 증명처럼 이를 계속 반복하면 언젠가는 모든 노드의 차수가 2 이하고 결국 두 형태 중 하나가 된다.

 

이 관찰 2 덕분에 NP처럼 보이는 문제가 다항 시간의 알고리즘을 가진다. 무려 일반 그래프에서 이 문제를 $O(N^6)$에 해결이 가능하다. 자세한 원리는 모르지만 $O(N^2)$개의 모든 볼을 그래프에서 제거해준 뒤 지배 그래프가 Path임을 가정해서 다익스트라 비슷하게 하는 것 같다. 만약 지배 그래프가 무조건 Path임이 보장되면 $O(N^4)$에도 해결이 되는 것이다.

 

일반 그래프에서 다항 시간 알고리즘을 가지기 때문에 다양한 특수한 그래프에서도 당연하게도 다항 시간 알고리즘을 가진다.

 

트리에서는 $O(N)$로 해결이 가능하다. 관찰 1만 가지고 $O(N^2)$ 알고리즘으로 해결할 수 있고 (대전 리저널에 출제됐었다. BOJ 14951 Broadcast Stations) 관찰 2 덕분에 모든 지배 정점이 트리의 지름 위에 있어 $O(N)$으로 해결이 된다. 

트리의 지름을 구하고 적당히 전처리를 하면 내가 출제한 문제(BOJ 34251 레몬티처럼 달콤한 입술)의 부분문제 1이 된다. 애초에 저걸 보고 자료구조로 해결이 될 것 같아서 출제한 문제다.

 

구간 그래프에서는 $O(N^2)$였나 $O(N)$이였나로 풀린다. 이것도 재밌을 것 같다.

 

내 심화 R&E에선 볼록 격자 그래프라는 신종 그래프를 정의해서 문제를 풀었다. 무조건 지배 그래프가 Path이며 심지어 좌표들이 등거리 변환을 잘 거치면 단조증가하게 만들 수 있어 $O(N^2)$ DP가 나오고 이를 분할 정복으로 최적화하면 $O(N \log^2 N)$까지 가능함을 보였다. 약간 개쩌는 연구같고 나중에 백준에 개인 문제로 출제를 해보고 싶다.