BOJ 16041. Double Clique

문제 링크

 

옛날에 나코더 셋에 있었던 문제인데, 풀이가 인상 깊어서 한 번 블로그에 남겨보려고 한다.

 

1. 문제 설명

무방향 그래프 $G$가 주어진다. 정점들의 집합을 $V$라고 하자. $G$의 여그래프 $G'$을 다음과 같이 정의하는데, 모든 $a, b \in V \ (a \neq b)$ 에 대해서 $G$ 에서 $a, b$를 잇는 간선이 있다면 $G'$에는 간선이 없고, $G$ 에서 $a, b$를 잇는 간선이 없다면 $G'$ 에는 간선이 있다. 클리크는 모든 노드 쌍이 연결된 정점 부분 집합을 의미하는데,

노드의 부분 집합 $S$ (공집합 포함)가 다음을 만족하면 더블 클리크 (Double clique)라고 정의한다.

1. $S$는 $G$에서 클리크이다.

2. $V-S$ ($S$를 제외한 나머지 노드 집합) 은 $G'$에서 클리크이다.

쉽게 말해, 다음과 같은 그래프를 의미한다.

S1, S2는 각각 더블 클리크이다.

 

여기서 우리는 이 $S$ 의 개수를 구해야 한다.

 

2. 풀이

기본적으로, 임의의 그래프에서 max 클리크를 구하는 것은 NP-Hard 임이 증명되었다. 그런데 하나도 아니라 두 개를 구하라니. 아무리 봐도 해결 방법이 떠오르지 않지만, 의외로 아주 간단한 그리디 알고리즘이 성립한다! 바로 차수($deg$)가 큰 순서로 S의 원소를 뽑는 것인데, 이를 통해 항상 더블 클리크를 만들 수 있음을 보이겠다.

 

Theorem. 1

그래프 G에서 더블 클리크가 존재한다면, G에서 더블 클리크를 이루는 임의의 정점의 집합 S에서
$\forall a \in S, \ deg(a) \ge |S|-1$ 이고, $\forall b \in V \setminus S, \ deg(b) \le |S|-1$ 인 S가 항상 존재한다.

 

즉, 각 정점의 차수가 $S$에 속한 원소는 일정 값 이상, 속하지 않는 원소는 일정 값 이하임을 보이는 것이다.

 

p.f )

그래프 $G$에서 어떤 더블 클리크 $S$가 있다.

$S$의 원소의 $deg$가 $|S|-1$ 이상임은 클리크의 정의에 의해서 자명하다. (각각 S의 다른 모든 원소와 간선이 있으므로)

 

그렇다면 $V \setminus S$ 는 어떨까?

$V \setminus S$ 의 원소는 다른 $V \setminus S$의 원소와는 간선이 존재하지 않으므로, 최대 $deg$는 $|S|$이다.

만약 $V \setminus S$ 의 모든 원소 $u$ 의 $deg(u) \le |S|-1$ 라면, 자연스럽게 본 가정을 만족한다.

 

만약 $V \setminus S$ 의 어떤 원소 $u$ 의 $deg(u) = |S|$ 라면, $S' = S + \{ u \}$ 또한 더블 클리크임을 알 수 있다.

그래프 $G $ 에서 $ u $ 는 다른 모든 $ S $ 의 원소와 간선이 있으므로 $ S' $ 은 클리크를 이루고, $V \setminus S$ 는 여전히 $ G $ 에서 간선 쌍이 존재하지 않기 때문이다.

즉, 이 $ S' $ 에서는 $$\forall a \in S', \ deg(a) \ge |S'|-1$$

$$\forall b \in V \setminus S', \ deg(b) \le |S| = |S'|-1$$ 을 만족함을 알 수 있다. ■

 

 

그리디 알고리즘이 성립함을 완벽히 보이려면, 한 단계를 더 나아가야 한다.

Theorem 2.

그래프 G에서 더블 클리크가 존재한다면, G에서 더블 클리크를 이루는 임의의 정점의 집합 S에서
$\forall a \in S, \forall b \in V \setminus S, \ deg(a) > deg(b)$ 인 S가 항상 존재한다.

 

p.f )

Theorem 1. 을 만족하는 그래프 $G$의 더블 클리크 $S$가 있다.

Theorem 1. 에 의해, Theorem 2. 를 만족하지 않는 경우는 다음밖에 없다.

$$\exists u \in S, \exists v \in V \setminus S, s.t. \ deg(u) = deg(v) = |S|-1 $$

이때, 이를 만족하는 $ u $ 는 오직 1개임을 알 수 있는데, $ v $ 는 $ u $ 를 제외하고 다른 모든 $ S $ 의 정점과 간선이 있기 때문이다.

그러니, $ S $ 의 다른 모든 원소의 $deg$는 $|S|-1+1 = |S|$ 이상이다.

 

이때, $ u $ 를 $ S $ 에서 제거한 $S' = S \setminus \{ u \}$ 또한 더블 클리크이다. $S'$ 은 $ G $ 에서 클리크를 이룸은 자명하고, $ u $ 는 $ S' $ 의 원소들과만 간선이 존재하므로, $V \setminus S'$ 또한 $G'$ 에서 클리크를 이룬다.

$S'$ 에서는 Theorem 2. 가 성립할까? 그렇다!

$$\forall a \in S', \ deg(a) \ge |S|$$

$$\forall b \in V \setminus S', \ deg(b) \le |S|-1$$

즉,

$$\forall a \in S', \forall b \in V \setminus S', \ deg(a) > deg(b)$$

가 성립한다. ■

 

 

이를 이용하면, 만약 더블 클리크가 존재한다면, 차수가 큰 순서대로 S의 원소를 뽑으면 무조건 더블 클리크를 찾을 수 있음을 알 수 있다.

그렇다면 개수는 어떻게 세야 할까? 이 또한 간단한 증명을 통해 고려해야 하는 상황을 보이겠다.

Theorem 3.

G의 더블 클리크 S가 주어진다면, 다른 더블 클리크는 모두 S에 최대 1개의 원소를 더했거나, 1개의 원소를 제거했거나, 1개의 원소를 더하고 1개의 원소를 제거한 형태이다.

 

p.f )

더블 클리크 $ S' $ 에 더블 클리크 $ S $ 에는 없는 다른 두 개의 원소 $ u $ , $ v $ 가 있다고 가정하자.

$u, v$ 는 모두 $V \setminus S$ 에 속하므로, $ u $ 와 $ v $ 사이에는 $ G $ 에서 간선이 존재하지 않는다.

하지만 $S'$ 에는 $u, v$ 모두 속하므로, $ u $ 와 $ v $ 사이에는 $G$ 에서 간선이 존재해야 한다. 즉, 모순이다.

 

같은 방법으로, $S'$ 에 $S$ 에는 있는 다른 두 개의 원소 $u$ ,$v$ 가 모두 없는 경우도 불가함을 보일 수 있다. ■

 

 

3. 결론

즉, 우리는 Theorem 2. 를 이용해 더블 클리크를 찾고, Theorem 3. 를 이용해 더블 클리크의 개수를 효과적으로 셀 수 있다.

총 알고리즘의 시간복잡도는 $O(N \cdot |S|) \simeq O(N \sqrt {M})$이다.