[Algorithm] Independent set and Vertex Cover
Independent Set Problem과 Vertex Cover Problem 에 Polynomial-Time Reduction 을 적용해보겠습니다.
먼저 Vertex Cover 의 정의부터 알아보겠습니다.
Definition of Vertex Cover
Graph G = (V, E) 에 대해 G의 모든 edge 들의 endpoint 를 적어도 하나 이상 포함하는 vetex set S ⊂ V 을 G 의 Vertex Cover 라고합니다.
즉 어떤 Vertex Set 이 Vertex Cover 라면 ∀ (i, j) ∈ E 에 대하여 i ∈ S or j ∈ S 가 성립합니다.
위의 그래프에서 {1,2,3,4,5,6} 은 Trivial 하게 G의 Vertex Cover입니다.
{2,5,4} 도 G의 Vertex Cover 입니다.
{1,3,6} 은 G의 Vertex Cover 가 아닙니다. ( Edge (2, 5) 의 Endpoint 를 Vertex Set {1,3,6} 이 Cover 하지 않기 때문입니다.)
이전 포스팅에서 다루었듯이, Indepedent Problem 은 Graph G 에 size 가 k 이상인 indepedent set 의 존재유무입니다.
Vertex Cover Problem은 Graph G에 size 가 k 이하인 Vertex Cover 의 존재유무입니다.
Indepedent Set Problem을 Vertex Cover Problem 으로 Reduce 할 수 있는지 살펴봅시다.
만약 S가 G의 Independent Set 이라면 (S 에 속하는 모든 원소는 서로 adjacent 하지 않음) V \ S 는 G의 Vertex Cover 가 될 것임을 직관적으로 알 수 있습니다. 하지만 이것이 타당한지 증명해보도록 하겠습니다.
Claim1 : Vertex Set S 가 Graph G 의 independet Set -> V \ S 는 Graph G의 Vertex Cover.
proof : S 가 G 의 Independent Set 이라면 G 에 속한 임의의 edge(u,v) ∈ E 에 대해서도 u ∉ S or v ∉ S입니다. 쉽게 설명하면 adjacent 한 vertex 들끼리는 Independent Set 에 함께 있을 수 없습니다. (Independent Set 의 정의) 따라서, u ∈ V \ S 이거나 v ∈ V \ S 를 만족해야합니다. 그러므로 V \ S 는 Vertex Cover 가 됩니다. (adjacent 한 Vertex 중 한쪽은 indendent Set 으로 가고 나머지 하나는 V \ S 에 존재하니, V \ S가 Vertex Cover 인 것은 당연합니다.)
비슷하게, 역방향의 증명을 통해 두 명제는 동치임을 보일 수 있습니다.
Claim2 : V \ S 가 G의 Vertex Cover -> S는 G의 indendent Set.
proof : V \ S 가 G의 Vertex Cover 이므로, ∀ i, j ∈ S에 대해 (i, j) 는 G 의 Edge 가 될 수 없습니다. ( 만약 (i, j) 가 G의 edge라면 V\S 가 Vertex Cover 라는 것에 모순입니다. ) 따라서 S 는 indendent Set 의 정의를 만족하므로, S = Independent Set 입니다.
이제 다시 Reduction 으로 돌아와 이야기해보겠습니다.
방금, S 가 Indendepnt Set 이면 V \ S 가 Vertex Cover 임을 보였습니다. 따라서 다음의 명제는 동치입니다. (if and only if)
Graph G 에 size 가 k 이상인 Independent Set 이 존재한다 <-> Graph G 에 size가 n-k 이하의 Vertex Cover 가 존재한다.
따라서 Indendent Set Problem의 Instance (G, k) 와 Vertex Cover Problem 의 instance (G, n-k)는 서로 동일한 답을 갖습니다. Reduction 이 가능할 조건 중 하나를 충족했습니다.
이제 Reduction 이 가능하기 위해서는 Instance of X 를 Instance of Y 로 바꿀 수 있어야함을 보여야 합니다.
Instance (G, k)가 주어지면 Instance(G, n-k)는 O(1) 에 Construct 할 수 있습니다. (숫자만 바꾸면 됩니다.)
따라서 Ix 를 Iy로 바꾸는 Algorithm R (Reduction)이 polynomial-time 에 동작하므로, Independent Set <= p Vertex Cover입니다. 그러므로 independent set 을 해결하는 efficient algorithm 이 존재하지 않는다면, vertex cover 를 해결하는 efficient algorithm 또한 존재하지 않습니다.