최대 클리크

1. 개요

최대 클리크 Maximum Clique
정의	모든 쌍이 서로 인접한 정점 집합 중 최대 크기
기호	클리크수 ω(G)
동치	ω(G) = 여그래프의 독립수 α = n − 여그래프의 정점덮개수 τ
복잡도	NP-난해 (Karp 1972) · 매개변수 k 에 대해 W[1]-완전
근사	n1−ε 근사가 NP-난해 (Håstad 1999 · Zuckerman 2007)
열거	Bron–Kerbosch (1973) + 피벗 — O(3n/3)
정확 해법	분지한정 + 탐욕 채색 상계 (MCQ · MCR · MCS · BBMC)
벤치마크	DIMACS Second Challenge (1992–93)

최대 클리크(maximum clique)는 그래프에서 모든 정점 쌍이 서로 인접하도록 고른 정점 집합 중 크기가 가장 큰 것이며, 그 크기를 클리크수 $\omega(G)$라 한다. “서로 전부 아는 사람들의 최대 모임”이라는 직관 그대로이며, 사교 모임에서 유래한 clique이라는 단어가 그대로 학술 용어가 됐다.

이 문제는 최대 독립집합·최소 정점 덮개와 여그래프 변환 하나로 완전히 같은 문제다.

$$\omega(G) = \alpha(\bar G) = n - \tau(\bar G)$$

세 문제 모두 카프(1972)의 21개 NP-완전 목록에 있고, 근사 불가능성 결과도 공유한다. 그 공통 부분(동치 관계, 갈라이 항등식, 근사 한계, 쉬운 그래프족)은 최대 독립집합 문서가 다루므로, 이 문서는 클리크 쪽에서만 자연스러운 것들 — 채색 상계를 쓰는 분지한정 계보, 극대 클리크 열거, 연속 완화, 매개변수 복잡도, 그리고 실제로 클리크 형태로 나타나는 응용 — 에 집중한다.

여그래프 변환이 공짜라면 왜 굳이 클리크로 푸느냐고 물을 수 있는데, 답은 밀도다. 실무 인스턴스는 대개 성긴 그래프(독립집합 쪽에 유리)이거나 조밀한 그래프(클리크 쪽에 유리) 중 한쪽으로 치우쳐 있고, 여그래프를 만들면 인접 행렬 크기가 통째로 뒤집힌다. 정점 100만 개짜리 성긴 소셜 그래프의 여그래프를 비트행렬로 들고 있으려는 시도는 대개 메모리에서 끝난다.¹

2. 채색이 만드는 상계 — 분지한정의 심장

정확 해법의 표준은 분지한정법이고, 그 성능은 거의 전적으로 상계의 품질이 결정한다. 클리크에서 쓰는 상계는 놀랄 만큼 간단하다.

후보 집합 $P$를 그래프 색칠했을 때 색이 $k$개 쓰였다면, $P$ 안의 클리크 크기는 $k$ 이하다.

이유는 한 줄이다. 클리크 안의 정점은 서로 전부 인접하므로 같은 색을 가질 수 없다. 따라서 클리크 크기 $\le$ 색 수. 채색을 최적으로 할 필요조차 없다 — 아무 탐욕 채색이나 돌려도 유효한 상계다. 현재 확정한 클리크 $R$과 상계 $k$, 지금까지 찾은 최선 $R^*$에 대해 $|R| + k \le |R^*|$이면 그 가지를 통째로 버린다.

여기에 얹히는 결정적 요령이 분지 순서다. 탐욕 채색은 정점마다 색 번호 $c(v)$를 남기는데, 이 번호를 큰 것부터 골라 분지하면 색 번호가 작은 정점들에 도달할 즈음에는 상계가 이미 충분히 낮아져 가지치기가 폭발적으로 일어난다. 채색을 상계인 동시에 분지 전략으로 쓴다는 이 아이디어가 토미타 계열 알고리즘의 핵심이다.

계보는 대략 이렇다.

• MCQ (토미타·세키, 2003) — 탐욕 채색 상계 + 색 번호 내림차순 분지를 정식화.
• MCR (토미타·카메다, 2007) — 초기 정렬과 전처리를 다듬어 상수를 깎음.
• MCS (토미타 외, 2010) — 채색 결과를 재배치해 상계를 더 조이는 기법(re-coloring)을 추가. MCR 대비 여러 인스턴스에서 자릿수 단위로 빨라졌다.
• BBMC / BBMCX (산 세군도 외) — 인접 관계를 비트셋으로 들고 채색과 후보 갱신을 워드 단위 AND/OR로 처리. 알고리즘이 아니라 자료구조로 얻은 속도이며, 조밀 그래프에서 특히 효과가 크다.
• cliquer (외스테르고르, 2002) — 정점을 하나씩 늘려 가며 부분 그래프의 최적값을 기억하는 방식. 채색 상계 계열과 다른 축이며 지금도 표준 비교군이다.

이 상계는 반정부호 계획법의 로바스 세타 함수보다 훨씬 느슨하지만, 노드마다 마이크로초 단위로 계산된다는 점이 모든 것을 이긴다. 분지한정에서 상계의 가치는 품질 × 노드 처리량이지 품질만이 아니다.²

3. 극대 클리크 전체 열거 — Bron–Kerbosch

“가장 큰 것 하나”가 아니라 극대 클리크를 전부 나열해야 하는 응용이 의외로 많다. 표준은 브론-케르보슈(1973) 재귀다. 상태는 세 집합이다.

• $R$ — 지금까지 확정한 클리크
• $P$ — 아직 넣어 볼 수 있는 후보
• $X$ — 이미 다른 가지에서 처리한 정점(중복 출력 방지)

$P$와 $X$가 둘 다 비면 $R$이 극대 클리크이므로 출력하고, 아니면 $P$의 각 정점 $v$에 대해 $R \cup \{v\}$, $P \cap N(v)$, $X \cap N(v)$로 재귀한 뒤 $v$를 $P$에서 $X$로 옮긴다.

순진한 버전은 극대가 아닌 클리크를 향해 헛돌기 때문에 피벗팅이 사실상 필수다. $P \cup X$에서 피벗 $u$를 하나 골라, $N(u)$에 속한 정점은 분지 대상에서 뺀다. 어떤 극대 클리크든 $u$를 포함하거나 $u$의 비이웃을 하나는 포함해야 하므로 완전성이 유지되고, $|P \setminus N(u)|$가 작아지도록 $u$를 고르면 분지 폭이 확 줄어든다.

무어-모저(1965)가 정점 $n$개 그래프의 극대 클리크 개수 최댓값이 $3^{n/3}$임을 보였고, 피벗을 쓴 브론-케르보슈의 최악 시간이 정확히 $O(3^{n/3})$임이 증명되어 출력 크기 기준으로 최적이다. 성긴 그래프에서는 퇴화도(degeneracy) 순서로 바깥 루프를 돌리는 변형이 $O(d\,n\,3^{d/3})$을 주는데, 실제 네트워크의 $d$가 수십 수준이라 정점 수백만 개 그래프에서도 돈다.

4. 연속 완화 — 모츠킨-슈트라우스

조합 문제를 굳이 연속 최적화로 바꾸는 길도 있다. 모츠킨과 슈트라우스(1965)는 표준 단체 $\Delta = \{x \ge 0 : \sum_i x_i = 1\}$ 위에서

$$\max_{x \in \Delta} \; \sum_{(i,j) \in E} x_i x_j \;=\; \frac{1}{2}\left(1 - \frac{1}{\omega(G)}\right)$$

임을 보였다. 즉 클리크수가 이차계획의 최적값에 통째로 인코딩된다. 최댓값은 최대 클리크 위에 균등하게 질량을 실을 때 달성된다.

물론 이걸로 문제가 쉬워지지는 않는다. 목적함수가 비볼록이라 국소해가 잔뜩 있고, 결국 NP-난해가 “비볼록 QP는 어렵다”로 번역됐을 뿐이다. 그럼에도 쓸모는 있다. 복제자 동역학(replicator dynamics)이나 투영 경사법을 이 형태에 얹으면 극대 클리크로 수렴하는 매끄러운 휴리스틱이 되고, 정규화 항을 얹어 국소해의 지형을 손보는 변형이 컴퓨터 비전 쪽에서 널리 쓰였다. 볼록 최적화의 도구를 비볼록에 밀어 넣었을 때 벌어지는 일의 교과서적 사례이기도 하다. 튜란 정리의 짧은 증명이 이 항등식에서 바로 나온다는 것도 유명한 부산물이다.

5. 어려움의 결이 다르다 — 매개변수 복잡도

“$k$-클리크가 있는가”를 $k$가 작을 때만 물으면 쉬워지지 않을까? 자명한 알고리즘은 $O(n^k)$다. 그런데 이걸 $f(k) \cdot n^{O(1)}$로 만드는 것, 즉 고정 매개변수 다루기 쉬움(FPT)은 불가능하다고 믿어진다 — 다우니와 펠로우즈가 클리크 문제가 W[1]-완전임을 보였고, 이것은 매개변수 복잡도 계층에서 “쉬운 쪽(FPT)에 속하지 않는다”의 표준 증거다. 나아가 지수시간 가설(ETH) 하에서 $n^{o(k)}$ 알고리즘조차 없다.

이 점이 클리크와 정점 덮개를 가르는 지점이다. 정점 덮개는 $k$를 매개변수로 하면 $O(1.2738^k + kn)$ 같은 FPT 알고리즘이 있고 커널화도 잘 되지만, 그 여집합인 독립집합/클리크는 $k$ 매개변수화에서 W[1]-완전이다. 같은 문제인데 매개변수를 어디에 붙이느냐가 계급을 바꾼다.

빠른 알고리즘이 아예 없는 것은 아니다. $k$가 3의 배수일 때 행렬 곱셈을 써서 $O(n^{\omega k/3})$에 $k$-클리크를 찾는 네셰트르질-폴략의 방법이 있다($\omega$는 여기서 행렬곱 지수 — 클리크수 기호와 겹치니 문헌을 읽을 때 조심해야 한다). 삼각형 개수 세기가 $O(n^{\omega})$인 것이 $k=3$ 경우다.

6. 벤치마크와 현실

DIMACS Second Implementation Challenge(1992–93)가 남긴 클리크 인스턴스 모음이 30년 넘게 표준 시험대다. 대표 계열만 보면

• C{n}.9 — 밀도 0.9의 무작위 그래프. 밀도가 높을수록 채색 상계가 무뎌져 어렵다.
• brock — 탐욕 휴리스틱을 일부러 속이도록 최적 클리크를 숨겨 놓은 그래프.
• keller — 켈러 추측에서 유래한 구조적 그래프. 큰 것은 여전히 부담스럽다.
• MANN — 슈타이너 삼중계에서 온 인스턴스. 상계는 잘 나오는데 하계를 못 올려 간극이 안 닫힌다.
• p_hat, san, gen — 차수 분포를 넓게 흩거나 최적해를 심어 놓은 계열.

여기서 배우는 교훈은 늘 같다. 난이도를 결정하는 것은 크기가 아니라 밀도와 구조다. 정점 200개짜리 조밀 무작위 그래프가 아직도 버티는 반면, 정점 수백만 개짜리 실제 네트워크는 축소 규칙과 퇴화도 순서만으로 몇 초에 끝난다. 실제 그래프의 클리크수는 대개 퇴화도 $d$에 비해서도 훨씬 작고, “$k$-코어에 속하지 않는 정점은 크기 $k$ 클리크에 못 들어간다”는 자명한 규칙 하나로 그래프가 통째로 날아가기 때문이다.

7. 클리크가 자연스럽게 나오는 곳

여그래프로 뒤집으면 독립집합 문제와 같지만, 문제가 클리크 형태로 태어나는 응용이 따로 있다.

• 대응 그래프 매칭. 두 구조의 정점 쌍을 새 정점으로 놓고 “양쪽에서 관계가 일치하는” 쌍끼리 간선을 이으면, 최대 클리크가 곧 최대 공통 부분구조다. 분자 구조 비교, 단백질 표면 정합, 분자 도킹의 특징점 대응, 3D 점군 정합의 대응쌍 선별이 전부 이 틀이며, 이쪽 문헌은 언제나 클리크 언어로 말한다.
• 컴퓨터 비전의 이상치 제거. 특징점 대응 후보들 사이에 “거리 관계가 서로 모순되지 않음”을 간선으로 놓으면, 가장 큰 상호 일관 집합이 최대 클리크다. RANSAC 계열의 결정론적 대안으로 쓰인다.
• 군집·커뮤니티 탐지. 소셜·금융 네트워크에서 완전 연결 부분군을 찾는 것이 그대로 클리크다. 순수 클리크는 너무 엄격해서 실무에서는 $k$-plex, $\gamma$-quasi-clique 같은 완화 개념을 쓰지만, 알고리즘 골격은 같은 분지한정이다.
• 부호 이론과 조합 설계. 최소 거리 조건을 만족하는 부호어들끼리 간선을 이으면 최대 부호 크기가 곧 클리크수다. 벤치마크의 MANN 계열이 슈타이너 삼중계, keller 계열이 정육면체 타일링 문제에서 온 것처럼, 순수 조합·기하 문제가 클리크 인스턴스로 번역되는 경로가 이것이다.
• 일정 조율. 서로 양립 가능한 작업 쌍을 간선으로 놓으면 동시에 배치 가능한 최대 집합이 클리크다.

한편 클리크수와 채색수의 관계도 짚어 둘 만하다. 언제나 $\omega(G) \le \chi(G)$지만 간극은 얼마든지 벌어진다 — 삼각형이 하나도 없는데($\omega = 2$) 채색수가 임의로 큰 그래프가 존재한다(미시엘스키 구성이 대표적이다). 그래서 채색 상계는 안전하지만 무뎌질 수 있고, 그 간극이 $0$인 그래프족이 바로 완전 그래프(perfect graph)다.³ 반대 방향에서는 램지 이론이 “정점이 충분히 많으면 큰 클리크나 큰 독립집합 중 하나는 반드시 있다”고 말하는데, 그 한계값을 정하는 문제 자체가 조합론의 대표적 난제로 남아 있다.⁴

8. 관련 문서

• 최대 독립집합 · 최소 정점 덮개 · 쾨니그 정리 · 딜워스 정리
• 분지한정법 · 절단평면법 · 정수계획법 · 반정부호 계획법
• 조합 최적화 · 근사 알고리즘 · 볼록 최적화
• 그래프 색칠 · 램지 이론 · NP-완전 · 유일 게임 추측
• 분자 도킹 · 그래프 분할 · 타부 서치

9. Footnotes

1. 그래서 논문 제목에 “sparse”가 붙으면 십중팔구 독립집합·정점 덮개 쪽이고, “dense”가 붙으면 클리크 쪽이다. 같은 문제를 두 이름으로 부르는 이유가 순전히 자료구조 때문이라는 건 좀 허무하지만, 메모리는 이론을 봐주지 않는다. ↩

2. 세타 함수 상계를 매 노드에서 계산하겠다는 아이디어는 주기적으로 재발명되는데, SDP 한 번 푸는 시간에 탐욕 채색을 수십만 번 돌릴 수 있다는 사실 앞에서 대부분 조용히 사라진다. 루트 노드에서 한 번만 계산해 전역 상계로 쓰는 절충은 실제로 쓰인다. ↩

3. 완전 그래프의 정의가 “모든 유도 부분그래프에서 $\omega = \chi$“이고, 강완전그래프 정리(추드노프스키·로버트슨·시모어·토머스, 2006)가 이를 홀수 구멍·홀수 반구멍의 부재로 특징지었다. 논문 분량이 150쪽이 넘는다. “간극이 0인 그래프를 전부 찾아라”라는 한 줄 질문의 대가다. ↩

4. 램지 수 $R(5,5)$조차 정확한 값을 모른다. 에르되시의 유명한 농담이 있다 — 외계인이 쳐들어와 $R(5,5)$를 못 대면 지구를 멸망시키겠다고 하면 인류의 컴퓨터를 총동원해 1년 안에 답을 낼 수 있겠지만, $R(6,6)$을 요구하면 차라리 외계인을 선제공격하는 편이 낫다고. ↩