클릭 문제

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

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

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