[Algorithm] Reduction on Independet Set and Cliques

그래프 G(V,E) 의 Independent Set 을 구하는 문제는 Cliques 를 구하는 문제로 reduction 할 수 있습니다.

 

먼저 Indepedent Set 과 Clique 의 정의에 대해 알아보도록 하겠습니다.

 

Definition of Indepedent Set

Graph G(V, E) 에 대해 Vertex set V’ ⊂ V 에 속한 모든 vertex 들이 서로 adjacent 하지 않으면 V’ 은 G 의 independent set 입니다. ( ∀ i, j ∈ V', (i, j) ∉ E 이면 V' 은 그래프 G의 Indepedent Set )

 

Definition of Clique

Graph G(V, E)에 대해 Vertex set V’ ⊂ V 에 속한 모든 vertex 들이 서로 adjacent 하면 V’ 은 G 의 clique 입니다. ( ∀i,j ∈ V', (i, j) ∈ E 이면 V' 은 그래프 G의 Clique )

 

예시를 통해 Indepedent Set 과 Clique 의 정의에 대해 이해해봅시다.

위 그래프에서, vertex set {2, 4}, {2, 4, 5} 는 Independent Set 입니다. vertex set {3, 4}, {2, 4, 5, 3} 은 indepedent set 이 아닙니다.

 

위 그래프에서, vertex set {3, 4}, {1, 2, 3} 은 Clique 입니다. vertex set {2, 4}, {2, 4, 5} 는 Clique 이 아닙니다.

 

이제 Reduction 을 적용해봅시다.

 

먼저 Problem X 를 다음과 같이 정의하겠습니다.

Problem X : 그래프 G가 size k 이상인 Independent Set 을 가지고 있는지 판별

Instance of X : Graph G, non-negative integer k

 

그리고 Problem Y를 다음과 같이 정의하겠습니다.

Problem Y :  그래프 G가 size k 이상인 Clique 을 가지고 있는지 판별

Instance of Y : Graph G, non-negative integer k

 

증명하고자 하는 명제는 다음과 같습니다.

 

Problem X is reducible to Problem Y.

 

Problem X와 Y는 모두 Decision Problem 입니다. Decision Problem 의 Reduction from X to Y 을 증명하기 위해서는 다음 두가지를 증명해야했습니다.

 

1. 임의의 X의 Instance Ix 를 2번을 만족하는 Y의 Instance Iy 로의 변환이 가능해야합니다.
2. Instance Iy 에 대한 Y의 답을 이용하여 Instance Ix 에 대한 X의 답을 구할 수 있어야 합니다. Decision Problem 인 경우에 한하여 두 답은 언제나 동일해야 합니다. ( Ix 에 대한 X의 답 <=> Iy 에 대한 Y의 답 (if and only if 로 양방향으로 같다는 것을 증명해야합니다.) )

먼저 1번을 증명해보겠습니다. Independent set 의 instance (G, k) 을 Clique 의 instance (G’, k) 로 변환해보겠습니다. 이 때 G’ 은 vertex set 은 G 와 동일하면서 G 에서 edge 가 존재하지 않는 모든 두 vertex u, v 간에만 edge 가 존재하는 graph 입니다. (이 때 G’ 을 G 의 complement 라 합니다.) , ( G(V, E), G(V, E') , E' 은 ∀ i, j ∈ V,에 대해 ( i, j ) ∉ E -> ( i, j ) ∉  E' 을 만족하는 Edge Set 입니다.)

 

이제 2번의 성립을 증명해야합니다. 즉, Instance (G, k) 에 대한 X이 답이 Instance (G', k)에 대한 Y의 답과 일치해야합니다. 다음의 Lemma 를 이용하여 증명해보도록 하겠습니다.

 

Lemma : S가 G의 Independent Set of size k <-> S는 G'(G의 complement) 의 Clique of size k 입니다. (if and only if)

proof of Lemma
S를 그래프 G의 independent set 이라고 합시다.
i ) S ⊂ V, |S| >= k 에 대하여 ∀ i, j ∈ S, ( i, j ) ∉ E 입니다. 
ii ) G' (V, E') 에 대해  ∀ i, j ∈ S, ( i, j ) ∈ E' 입니다. (G' 의 정의)
그러므로 S가 G의 Independent Set of size k 이면 S는 G' 의 Clique of size k 입니다.

S'을 그래프 G의 Clique 이라고 합시다.
i ) S ⊂ V, |S| >= k 에 대하여 ∀ i, j ∈ S, ( i, j ) ∈ E 입니다.
ii ) G'(V, E') 에 대해 ∀ i, j ∈ S, ( i, j ) ∉ E' 입니다. (G' 의 정의)
그러므로 S가 G의 Clique of size k 이면 S는 G의 Independent Set of size k 입니다.

따라서 Lemma 에 의해 Problem Y를 해결함으로서 Problem X를 해결할 수 있습니다. 따라서 X <= Y 입니다.

 

그러므로 Problem X와 Problem Y에 대하여 다음과 같이 이야기할 수 있습니다.

 

Clique Problem 을 해결하는 알고리즘이 존재하면, Independent Set Problem 을 해결하는 알고리즘 또한 존재합니다.

Clique Problem 을 해결하는 것은 적어도 Independent Set Problem 을 해결하는 것만큼 어렵습니다.