Clique Problem
클릭 문제
[Input]
Graph \(G = (V, E)\)
Positive Integer \(k\)
[Query]
그래프 \(G\)에 크기가 \(k\)인 완전 부분 그래프(=Clique)가 존재하는가?
* Graph (그래프) (URL)
Mechanism (원리)
Implementation (구현)
Performance (성능)
Verification (검증)
Theorem. Clique Problem은 NP-Complete이다.
* 어떤 문제가 NP-Complete이려면, NP이고 NP-Hard이어야 한다.
- 이 때, NP-Hard임을 증명하는 것은
기존에 NP-Hard임이 증명된 문제를 해당 문제로 Reduction하여 논리적 관계를 보이는 것으로 이루어진다.
* 클릭 문제가 NP-완비임을 보이기 위해,
기존에 NP-완비임이 증명된 "3SAT 문제 (URL)"를 이용한다.
pf)
1. Clique Problem이 NP(Nondeterministic Polynomial) 임을 증명한다.
크기가 \(k\)인 완전 부분 그래프가 주어질 때,
(즉, 클릭 문제의 Query에 Yes라 답할 근거가 주어질 때)
이것의 크기가 \(k\)이고,
완전 그래프임은 다항식 시간에 확인할 수 있다.
그러므로, 클릭 문제는 NP이다.
(Clique Problem의 Optimum을 찾는데 다항식 시간이 걸린다는 뜻이 아니라,
최적해가 이미 주어져있다면, 그것이 최적해라는 근거를 보이는데 다항식 시간이 걸린다는 의미이다.
이것이 "Nondeterministic"의 의미이다.)
2. 3SAT Problem \(\leq_{p}\) Clique Problem 임을 증명한다.
3SAT의 Instance를 Clique의 Instance로 Reduction한다.
3SAT의 모든 Literal 각각에 정점을 하나씩 생성한다.
같은 Clause에 속하는 Literal끼리는 간선을 두지 않으며,
서로 Inversion관계에 있는 경우, 간선을 두지 않는다.
이 경우 외에는 모두 간선으로 연결한다.
(Literal의 총 개수를 \(k\)라 할 경우, 이러한 변환과정은 \(\Theta(k^2)\) 시간이 소요된다. 즉, 다항식 시간에 해결된다.)
위 그림은 3-CNF \((x_1 \lor x_2 \lor x_3) \land (\bar{x_1} \lor x_2 \lor x_3) \land (\bar{x_2} \lor \bar{x_3} \lor x_4)\) 에 대응되는
Graph를 표현한 그림이다.
3SAT Problem에서의
"Clause의 개수가 \(k\)개인 3-CNF는 만족 가능한가?"에 해당되는 Query는
Clique Problem에서의
"크기가 \(k\)인 완전 부분 그래프(클릭)가 존재하는가?"에 해당되는 Query로
대치할 수 있다.
이렇게 두 Query가 동치인 이유는 아래와 같다.
1) 3SAT의 Instance에서 만족 할당이 존재하면, 각 Clause에 최소한 하나 이상 True로 할당되는 Literal이 존재하게 된다.
각 Clause에서 True로 할당된 Literal을 하나씩 추출하면, 이들에 대응되는 정점 간에는 모두 간선이 존재하게 된다.
(서로 역의 관계에 있으면 동시에 True를 할당할 수 없음은 자명하기 때문이다.)
Clause의 총 개수가 \(k\)이므로, 이 정점들의 집합은 크기가 \(k\)인 완전 그래프를 이루게 된다.
2) Reduction된 그래프에 크기가 \(k\)인 완전 그래프가 존재한다면,
이를 구성하는 정점들은 \(k\)개의 Clause에서 각각 하나씩 유래된 것들이다.
(같은 Clause에 포함된 Literal간에는 간선이 없어야 한다는 제약이 있기 때문이다.)
완전 그래프는 모든 정점 간에 간선이 있어야 하기 때문에,
변환 규칙상, 이 완전 그래프에 속한 Literal들이 서로 역 관계에 있을 수 없다.
이 Literal들에 모두 True값을 할당하면 3SAT Instance의 만족 할당이 된다.
따라서, 3SAT Problem \(\leq_{p}\) Clique Problem 이다.
Reference: Introduction to Algorithms 3E (CLRS)
(Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein 저, MIT Press, 2018)
Reference: 쉽게 배우는 알고리즘
(문병로 저, 한빛아카데미, 2018)
