최대 독립집합

최적설계 수치해석 마지막 수정: 2026-08-17 04:26:41

1. 개요[편집]

최대 독립집합 Maximum Independent Set
정의	어느 두 원소도 인접하지 않은 정점 집합 중 최대 크기
기호	독립수 $\alpha(G)$
쌍대 관계	$\alpha(G) + \tau(G) = n$ (갈라이) · $\alpha(G) = \omega(\bar{G})$
복잡도	NP-난해 (Karp 1972, 클리크와 동치)
근사 한계	$n^{1-\varepsilon}$ 근사가 NP-난해 (Håstad 1999 · Zuckerman 2007)
쉬운 그래프족	이분 · 트리 · 현그래프 · 구간 · 완전그래프(perfect)
정확 알고리즘	분지한정 · Bron-Kerbosch · $O(1.1996^n)$ (Xiao–Nagamochi 2017)
주의	최대(maximum)와 극대(maximal)는 다른 문제

최대 독립집합(maximum independent set)은 그래프에서 어느 두 정점도 서로 인접하지 않도록 고른 정점 집합 중 크기가 가장 큰 것이며, 그 크기를 독립수 $\alpha(G)$ 라 한다. “서로 충돌하지 않는 것을 최대한 많이 고르라”는 요구는 스케줄링부터 주파수 할당까지 어디에나 나타나기 때문에, 이 문제는 조합 최적화에서 가장 자주 재발견되는 원형(原型) 중 하나다.

동시에 가장 어려운 문제이기도 하다. NP-난해라는 사실만으로는 부족하고 — 근사조차 사실상 불가능하다. 다항시간 알고리즘이 보장할 수 있는 근사비가 $n^{1-\varepsilon}$ 수준, 즉 “정점 하나를 답으로 내는 것”보다 상수 배 정도밖에 낫지 않다. 그런데도 실무에서는 수만 정점짜리 인스턴스가 분지한정법으로 초 단위에 풀린다. 최악 사례와 실제 사례 사이의 간극이 이만큼 벌어지는 문제도 드물다.¹

2. 세 개의 얼굴 — 덮개, 클리크, 독립집합[편집]

이 문제를 이해하는 첫걸음은 셋이 같은 문제임을 확인하는 것이다.

정점 집합 $I \subseteq V$ 에 대해 다음 세 명제는 동치다.

I \text{ 가 독립집합} \iff V \setminus I \text{ 가 정점 덮개} \iff I \text{ 가 여그래프 } \bar{G} \text{ 의 클리크}

첫 동치는 정의를 뒤집기만 하면 된다. $I$ 가 독립 ⟺ $I$ 안쪽에 간선이 없다 ⟺ 모든 간선이 끝점을 최소 하나 $V\setminus I$ 에 둔다 ⟺ $V \setminus I$ 가 최소 정점 덮개의 의미에서 덮개다. 크기를 세면 갈라이 항등식

\alpha(G) + \tau(G) = n

이 나온다. 둘째 동치는 인접 관계를 반전한 것뿐이라 $\alpha(G) = \omega(\bar{G})$ , 즉 독립수는 여그래프의 클리크수다.

셋이 동치라는 말은 복잡도가 완전히 붙어 다닌다는 뜻이다. 하나가 다항시간이면 셋 다 다항시간, 하나가 NP-난해면 셋 다 NP-난해. 카프(1972)의 21개 NP-완전 문제 목록에 클리크와 정점 덮개가 나란히 들어 있는 것도 이 때문이다.

그런데 근사비는 전혀 붙어 다니지 않는다. 정점 덮개에는 초등적인 2-근사가 있지만, 독립집합에는 상수 근사가 아예 없다. $n = 1000$ 이고 $\tau = 998$ , $\alpha = 2$ 인 그래프를 생각해 보자. 덮개를 999개 낸 알고리즘은 근사비 $1.001$ 의 훌륭한 성적이지만, 그 여집합은 크기 1이라 독립집합으로는 근사비 2다. 최적값에 붙는 작은 오차가 여집합에서는 상대적으로 폭발한다. 근사비라는 척도가 문제의 상보적 형태에 대해 얼마나 취약한지 보여 주는 교과서적 예다.²

3. 최대와 극대 — 헷갈리면 논문을 잘못 읽는다[편집]

용어 하나만 짚고 간다. 영어 약칭 MIS는 문헌에 따라 두 가지 다른 대상을 가리킨다.

maximum independent set — 크기가 최대인 것. NP-난해.
maximal independent set — 어떤 정점도 더 넣을 수 없는 것(극대). 탐욕적으로 선형 시간에 하나 찾을 수 있다.

극대 독립집합은 “정점을 하나씩 보면서 인접한 게 이미 없으면 넣는다”로 끝난다. $n$ 각형 경로에서 이 탐욕이 크기 $n/3$ 짜리 극대 집합을 낼 수 있지만 최대는 $n/2$ 인 것처럼, 극대는 최대와 얼마든지 멀어질 수 있다. 병렬·분산 알고리즘 문헌에서 말하는 MIS는 거의 항상 극대 쪽이며, 아래 루비의 알고리즘도 그렇다. 이걸 최대로 읽으면 “NP-난해 문제가 $O(\log n)$ 라운드에 풀린다”는 이상한 결론에 도달하게 된다.³

4. 근사 불가능성[편집]

하스타드(1999)가 근사 알고리즘에서 다룬 PCP 정리의 기계를 써서 보인 것은 다음이다. 임의의 $\varepsilon > 0$ 에 대해 $n^{1-\varepsilon}$ 근사는 NP $=$ ZPP가 아닌 한 불가능하다. 주커먼(2007)이 사용된 추출기를 결정론화해 가정을 P $\ne$ NP로 낮췄다.

$n^{1-\varepsilon}$ 이라는 수치의 의미를 실감하려면 자명한 알고리즘과 비교하면 된다. “정점 하나를 낸다”는 근사비 $\alpha \le n$ 을 자동으로 만족한다. 즉 반세기의 연구가 자명한 알고리즘 대비 얻어낸 것은 상수도 아니고 로그의 거듭제곱 정도로, 현재 최선이 파이게(2004)의 $O\!\left(n (\log\log n)^2 / (\log n)^3\right)$ 근사다.

차수가 $\Delta$ 로 제한되면 사정이 나아진다. 이때는 $O(\Delta \log\log \Delta / \log \Delta)$ 근사가 가능하고, 탐욕적으로 최소 차수 정점을 집는 것만으로 $(\Delta+1)/2$ 근사에 근접한 보장이 나온다. 격자나 메시처럼 차수가 상수인 실제 그래프에서 휴리스틱이 잘 먹히는 이유다. 그럼에도 $\Delta$ 가 큰 영역에서는 $\Delta / 2^{O(\sqrt{\log \Delta})}$ 보다 나은 근사가 NP-난해다.

상계 쪽에는 반정부호 계획법의 명작이 있다. 로바스 세타 함수 $\vartheta(G)$ 는 SDP로 다항시간에 계산되면서

\alpha(G) \;\le\; \vartheta(G) \;\le\; \chi(\bar{G})

를 만족한다(로바스 샌드위치 정리). 두 NP-난해량 사이에 다항시간으로 계산되는 값이 끼어 있는 희귀한 구조이며, 그래프 색칠과 독립집합을 잇는 다리이기도 하다.

5. 다항시간에 풀리는 그래프족[편집]

최악의 그래프가 절망적일 뿐, 구조가 있으면 대부분 무너진다.

이분 그래프. 쾨니그 정리에 갈라이 항등식을 얹으면 $\alpha = n - \nu$ , 즉 최대 매칭 한 번이면 끝난다. 이분 매칭의 홉크로프트-카프로 $O(E\sqrt{V})$ .
트리. 동적 계획법의 입문 예제다. 정점 $v$ 에 대해 “ $v$ 를 포함하는 최적”과 “포함하지 않는 최적”을 각각 $f_1(v) = 1 + \sum_{c} f_0(c)$ , $f_0(v) = \sum_c \max(f_0(c), f_1(c))$ 로 잎에서 올라오면 $O(n)$ . 가중치가 있어도 그대로다.
현그래프(chordal). 완전 소거 순서를 잡으면 단체 정점(simplicial vertex, 이웃들이 서로 다 인접한 정점)이 항상 존재한다. 단체 정점을 답에 넣고 그 닫힌 이웃을 통째로 지우는 탐욕이 최적임이 증명되며 $O(n+m)$ . 소거 순서 자체가 희소행렬 분해의 채움 최소화에 쓰이는 그 순서다.
구간 그래프. 현그래프의 부분족이고, 여기서는 문제가 곧 구간 스케줄링이다. 끝나는 시각이 이른 것부터 집는 탐욕이 최적이라는 사실이 학부 알고리즘 첫 주에 나오는데, 그게 사실 NP-난해 문제의 특수 케이스라는 점은 잘 언급되지 않는다.
완전 그래프(perfect graph). 그뢰첼-로바스-슈라이버(1981)가 타원체법과 세타 함수로 $\alpha$ 를 다항시간에 계산했다. 이론적으로만 다항시간인 대표적 사례로, 실무 코드는 여전히 조합적 알고리즘을 쓴다.
평면 그래프. 베이커의 기법(1994)으로 PTAS가 나온다. 그래프를 $k$ 겹 바깥평면 조각으로 쪼개고 각 조각을 트리 분해로 정확히 푼 뒤 이어 붙이는 방식.

6. 정확 알고리즘 — 분지한정과 Bron-Kerbosch[편집]

지수시간을 각오하고 정확한 답을 원할 때의 표준 도구는 두 가지다.

분지한정. 정점 $v$ 를 골라 “ $v$ 를 넣는다(그리고 $N[v]$ 를 지운다)” 대 “ $v$ 를 뺀다”로 가르는 것이 기본 분지다. 여기에 강력한 상계가 붙는다. 남은 그래프를 탐욕적으로 그래프 색칠하면 색 수가 클리크수의 상계가 되므로(여그래프 관점), 현재 최적해를 넘길 수 없는 가지를 통째로 자를 수 있다. 토미타의 MCS/MCR, 외스테르고르의 cliquer 계열이 이 방식이며, 밀도가 낮은 실제 그래프에서는 수만 정점도 처리한다. 차수 1·2 정점 제거, 지배 정점 제거 같은 축소 규칙을 전처리로 돌리면 인스턴스가 통째로 사라지는 일도 흔하다.

Bron-Kerbosch(1973). 최대 하나가 아니라 극대 클리크 전체를 열거하는 재귀 알고리즘이다. 현재 클리크 $R$ , 후보 $P$ , 제외 $X$ 를 들고 다니며 $P$ 와 $X$ 가 모두 비면 $R$ 을 출력한다. 순진한 버전은 중복 탐색이 심해서, $P \cup X$ 에서 피벗을 골라 그 이웃을 분지에서 빼는 최적화가 필수다. 무어-모저(1965)가 정점 $n$ 개 그래프의 극대 클리크 개수가 최대 $3^{n/3}$ 임을 보였고, 피벗을 쓴 Bron-Kerbosch의 최악 시간이 정확히 $O(3^{n/3})$ 이므로 출력 크기 기준으로 최적이다.⁴

지수의 밑을 깎는 경쟁도 계속된다. 타잔-트로야노프스키(1977)의 $O(2^{n/3}) \approx O(1.26^n)$ 에서 시작해, 현재 다항 공간 최선은 샤오-나가모치(2017)의 $O(1.1996^n)$ 이다. 밑이 $2$ 에서 $1.2$ 로 내려온 것이라 $n=100$ 에서 대략 $10^{22}$ 배 차이 — 지수 알고리즘의 상수가 왜 중요한지 보여 주는 사례다.

7. 병렬 — 루비의 알고리즘[편집]

극대 독립집합은 순차적으로는 지루할 만큼 쉽지만, 병렬로는 흥미로운 문제다. 탐욕은 본질적으로 순차적이라(“앞 정점의 결정을 봐야 한다”) 병렬화가 자명하지 않다.

루비(1986)와 알론-바바이-이타이(1986)가 독립적으로 낸 무작위 알고리즘은 이렇다. 각 라운드에서

모든 정점 $v$ 가 난수 $r(v)$ 를 뽑는다.
이웃 전원보다 $r(v)$ 가 작으면 $v$ 를 독립집합에 넣는다.
선택된 정점과 그 이웃을 전부 지운다.

각 라운드에서 간선의 기대 절반 이상이 제거되므로 기댓값 $O(\log n)$ 라운드에 끝나고, 문제가 NC에 속함을 보인다. 라운드마다 통신이 이웃 한 겹뿐이라 분산 환경에도 그대로 얹힌다.

이게 수치해석에서 갖는 의미는 크다. 대칭 파괴(symmetry breaking)가 필요한 곳마다 등장하기 때문이다.

다중격자법의 조립자 선택. 러기-슈튀벤 C/F 분할과 대수적 다중격자법의 응집(aggregation) 단계는 강연결 그래프 위에서 극대 독립집합을 찾아 조대 격자 점을 고른다. “서로 강하게 연결되지 않은 점들을 골고루 뽑는다”가 정확히 독립집합의 요구다.
메시 색칠과 병렬 조립. 유한요소 행렬 조립이나 가우스-자이델 완화를 GPU에서 돌리려면 같은 자유도에 동시에 쓰는 요소가 없어야 한다. 요소 인접 그래프의 독립집합 단위로 배치를 나누는 것이 표준이며, 메시 생성 후처리로 붙어 있는 경우가 많다.

8. 응용[편집]

스케줄링. 시간이 겹치는 작업을 간선으로 놓으면 최대 독립집합이 곧 동시 수행 가능한 최대 작업 수다. 구간 그래프면 탐욕으로 최적, 자원이 여럿이면 곧장 NP-난해로 넘어간다.
주파수·채널 할당. 간섭 그래프에서 동시에 송신 가능한 링크 집합이 독립집합이다. 무선 스케줄링에서 “최대 가중 독립집합을 매 슬롯 푸는” 정책이 처리량 최적임이 알려져 있는데, 그 정책이 NP-난해라 실제로는 탐욕 근사를 쓴다.
분자 그래프 매칭. 두 분자의 최대 공통 부분구조(MCS)를 찾는 표준 기법이 대응 그래프(product/association graph)를 만들고 거기서 최대 클리크를 찾는 것이다. 두 그래프의 정점 쌍을 새 정점으로 두고, 양쪽에서 관계가 일치하는 쌍끼리 간선을 잇는다. 케모인포매틱스의 유사도 계산, 파마코포어 정렬, 단백질 구조 비교, 분자 도킹의 특징점 대응이 전부 이 틀을 쓴다. 정점 수가 두 분자 크기의 곱이라 인스턴스가 금세 커지고, 그래서 Bron-Kerbosch 구현 품질이 곧 성능이 된다.
오류정정부호. 부호어 사이 거리를 조건으로 놓은 그래프의 독립집합이 부호 자체이며, 섀넌 용량이 로바스 세타 함수의 원래 동기였다.

9. 관련 문서[편집]

DIMACS 클리크 벤치마크에는 정점 수 200개인데 아직 아무도 최적해를 증명하지 못한 인스턴스(C250.9 계열의 친척들)가 있는 반면, 소셜 네트워크에서 뜯어온 정점 수백만 개짜리 희소 그래프는 축소 규칙만으로 통째로 사라진다. 문제의 난이도는 크기가 아니라 밀도와 구조가 결정한다. ↩
근사비가 상보 변환에 취약하다는 이 현상은 “최대화 문제와 그 여집합 최소화 문제는 근사 관점에서 다른 문제”라는 일반 원리의 사례다. 그래서 근사 알고리즘 논문 제목은 늘 최대화인지 최소화인지를 명시한다. 대충 “정점 덮개 잘하니까 독립집합도 잘하겠지”라고 넘겼다가는 지도교수에게 혼난다. ↩
maximal과 maximum을 우리말로는 극대와 최대로 깔끔히 구분하는데, 정작 국내 논문에서도 영어 약칭 MIS를 그대로 쓰다 보니 같은 혼동이 수입된다. 분산 알고리즘 논문에서 MIS가 $O(\log n)$ 에 풀린다고 나오면 그건 100% 극대 쪽이다. ↩
무어-모저 그래프는 정점을 3개씩 묶어 삼각형 없는 완전 다분 그래프를 만든 것으로, 극대 클리크가 정확히 $3^{n/3}$ 개다. 열거 알고리즘의 최악 사례가 이렇게 아름답게 딱 떨어지는 경우는 흔치 않다. ↩