클릭 문제

크기가 3인 클릭을 갖는 그래프

클릭 문제 (clique problem)는 NP완전인 그래프 이론에 등장하는 문제이다. 이 문제는 리처드 카프가 1972년 논문에서 NP완전임을 증명한 21문제 중의 하나일 뿐만 아니라, NP완전 문제 이론을 소개한 쿡의 논문에서도 언급된 유명한 문제이다.

그래프의 클릭(clique)이란 부분그래프이면서 그래프의 임의의 두 노드가 서로 연결된 것으로 정의된다. 즉, 완전 그래프인 부분그래프를 클릭이라 한다. 오른쪽 그림에서 노드 1, 2, 5로 이루어진 부분그래프는 클릭이 된다. 왜냐하면, 각 노드가 모든 나머지 노드와 연결되어 있기 때문이다. 반면 2, 5, 3으로 이루어진 그래프를 보면, 5와 3이 연결되어 있지 않아 클릭이 되지 못한다.