[Algorithm] Polynoimal-time Reduction from 3-SAT problem to Independent Set Problem

3-SAT Problem 을 Independent Set Problem 으로 Reduction 하는 과정에 대해 살펴보도록 하겠습니다. 본론에 들어가기 앞서 문제를 이해하기 위한 개념들을 살펴보도록 하겠습니다.

 

Definition

Literal : Literal 은 Boolean variable xi 나 그 부정 (negation) ¬xi 을 의미합니다.

Clause : Clause 는 literal 들의 disjunction (논리합 ∨) 을 의미합니다.

Conjunctive Normal Form :  Conjuctive Normal Form은 clause 들의 conjunction (논리 곱 Λ) 으로 표현된 proportional formula (명제 식) 을 뜻합니다.

 

(x1 ∨ x2 ∨ ¬ x4 ) ∧ (x2 ∨ ¬ x3 ) ∧ x5 는 CNF formula 입니다.

 

CNF formula F 의 각 clause 가 정확히 k 개의 literal 로 구성되어 있다면, F 는 k-CNF formula 라고합니다.

(x1 ∨ x2 ∨ ¬ x4 ) ∧ (x2 ∨ ¬ x3 ∧ x5 ) 는 3-CNF formula 입니다.

(x1 ∨ x2 ∨ ¬ x4 ) ∧ (x2 ∨ ¬ x3 ) 는 3-CNF formula 가 아닙니다.

 

이제 SAT Problem 이 무엇인지 알아보도록 하겠습니다.

 

Definition of SAT Problem : CNF Formula F 가 주어졌을 때, F의 값이 True 가 되도록 F의 각 variable 에 true/false 를 assign 할 수 있는지 판별하는 문제입니다. Assign 할 수 있는 경우 F는 Satisfable 하다고 합니다.

 

그 중 3-CNF Formula F 에 대한 Satisfiability Problem 을 3-SAT 라고 합니다.

 

3-SAT Problem 의 중요한 성질들을 살펴보도록 하겠습니다.

• F가 True가 되게 하는 variable assignment 를 찾는 다는 것은 F의 variable 들에 해당하는 값들을 assignment 하면 F의 각 Clause 가 모두 True 가 된다는 것을 의미합니다.
• 각 Clause 에서 적어도 하나의 literal 만 true 이면 F는 무조건 true 가 됩니다. (Clause는 모두 disjunction으로 연결되어 있기 때문입니다.) 따라서 F의 각 clause 에서 literal 하나씩을 골라 그들을 모두 true가 되게하는 assignment 가 존재하는지 여부를 확인해주면 됩니다.
• 각 clause 에서 literal을 하나씩 뽑을 때 xi와 ¬xi 는 같이 선택할 수 없으며, 이와 같이 선택한 경우 confiliction 이 일어났다고 합니다.

그렇다면 Polynoimal-time Reduction from 3-SAT problem to Independent Set Problem 은 다음과 같이 설명할 수 있습니다.

 

1. Instance of 3-SAT Problem 을 Instance of Independent set Problem 으로의 Convert 하는 Polynomial time Algorithm R의 존재,

2. Instance of 3-SAT Problem 의 Answer가 Y <=> Instance of Independent Set Problem 의 Answer가 Y

 

이제 1번에 대해 생각해봅시다. 어떻게하면 Instance of 3-SAT Problem (= F) 를 Independent Set Problem (= G(V, E) ) 로 Convert 할 수 있을까요?

 

다음과 같이 생각해봅시다.

• F의 각 literal 에 대해, 이에 대응하는 Gf 의 unique 한 vertex 가 존재합니다. (F의 literal을 Vertex로 생각합시다.)
• F의 각 clause를 구성하는 3개의 literal 들은 Gf에서 서로 triangle 을 이룹니다. 따라서 Gf의 independent set 은 각 clause 의 literal 들에 대응하는 vertex 3개 중 최대 한 개만을 포함하게 됩니다. (clause 에 속한 두 literal 을 고르는 순간 두 literal에 대응하는 vertex 사이에는 edge가 존재합니다.)
• xi와 ¬xi가 존재한다면, Gf 에서 이 둘을 edge로 이어줍니다. 이렇게하면, Gf의 Independent Set 에 대응하는 literal 들은 confliction 이 일어나지 않습니다. (Complement 관계에 있는 literal 간에는 edge가 존재하므로 Gf 의 Independent Set에는 그 두 literal이 포함될 수 없습니다.)
• Instance of Independent Set Problem 의 size k는 F를 구성하는 clause 의 총 개수로 둡니다.

 

Conjunctive Normal Form F와 Gf의 예시

이렇게하면, Instance of 3-SAT Problem 을 Instance of Independent Set Problem 으로 convert 할 수 있습니다. 그리고 Gf 를 Construct 하는 것은 F의 각 literal 을 읽을 때마다 Graph Vertex와 edge를 추가해주면 되므로, linear time 에 만들 수 있습니다.

 

이제, 2번에 대해 생각해봅시다.

i) Instance of 3-SAT Problem 의 Answer가 Y => Instance of Independent Set Problem 의 Answer가 Y

proof : F를 Satisfiable 하게 만드는 assignment 가 존재한다고 합시다.

이 경우, 해당 assignment 에서 F의 각 clause 마다 true 값이 되는 literal 을 하나씩 고르면 해당 literal 에 해당하는 vertex 들은 Gf의 independent set 이 됩니다. 이유에 대해 설명하겠습니다.

assignment 에 해당하는 literal 에 대응되는 vertex set 을 L 이라고 합시다. 그러면 ∀ u, v ∈ L 에 대하여, u와 v는 서로 다른 triangle 에 속합니다. 그리고 u, v 는 comlement 관계가 아니므로 edge (u,v) 가 존재하지 않습니다. 따라서 L 은 Independent Set 입니다.

Clause 가 총 k개 있으므로, 이 경우 Gf는 size 가 k 인 independent set 을 가지게 됩니다.

 

ii) Instance of 3-SAT Problem 의 Answer가 Y <= Instance of Independent Set Problem 의 Answer가 Y

S가 Size k 인 Gf 의 independent set 이라고 합시다. Claim 이 성립하기 위해서는

ii-1) S는 각 clause 에 대응하는 3개의 vertex 들 중 정확히 하나를 포함해야 합니다. (만약, 같은 clause 내의 두 vertex를 포함하는 경우, independent set 의 정의를 위반합니다.)

ii-2) S는 confliction 관계에 있는 두 literal 에 해당하는 vertex 두 개를 모두 포함할 수 없습니다. (Gf에서 complement 관계에 있는 vertex는 edge가 존재하므로 Gf의 independent set 에는 complement 관계의 두 vertex가 속할 수 없습니다.)

 

따라서 S에 속한 vertex 에 대응하는 literal 들이 true가 되도록 F의 variable 들에 assign 하면, F를 구성하는 모든 clause 들은 true가 되며, 따라서 F는 true가 됩니다.

 

1과 2를 만족하므로, (3-SAT) <= p (Independent Set)이며, Independent Set Problem 을 Polynomial-Time 에 해결하는 Algorithm 이 존재하면, 3-SAT을 해결하는 Polynomial-Time Algorithm 도 존재합니다. 그리고 3-SAT Problem 을 해결하는 Polynomial-time algorithm이 존재하지 않으면 Independent Set 을 polynomial-time 에 해결할 수 없습니다.