커니핸-린 알고리즘

최적설계 수치해석 마지막 수정: 2026-08-14 04:12:18

1. 개요[편집]

커니핸-린 알고리즘 Kernighan–Lin Algorithm
발표	Brian W. Kernighan, Shen Lin (벨 연구소, 1970)
푸는 문제	균형 이분할의 절단 최소화 (국소 개선)
기본 동작	양쪽에서 한 개씩 골라 맞교환
이득 공식	$g_{ab} = D_a + D_b - 2c_{ab}$
패스 비용	소박한 구현 $O(n^3)$, 원 논문 $O(n^2\log n)$
후계자	피두치아-마테이시스(FM, 1982) — 패스당 선형
현재 지위	다단계 분할의 세련화(refinement) 단계

1970년에 나온 휴리스틱이 아직도 현역인 이유는, 그게 좋아서가 아니라 좋은 초기값 위에서 쓰면 좋아서다.

커니핸-린 알고리즘(Kernighan–Lin, KL)은 이미 주어진 균형 이분할을 출발점으로 삼아, 양쪽 조각에서 정점을 하나씩 골라 맞바꾸는 연산만으로 절단 간선 가중치를 줄여 나가는 국소 개선 휴리스틱이다. 1970년 벨 연구소의 브라이언 커니핸과 셴 린이 발표했다.¹ 맞교환만 쓰기 때문에 두 조각의 크기가 저절로 그대로 유지된다는 것이 이 설계의 첫 번째 미덕이고, 당장 손해인 교환도 일단 저지른 뒤 나중에 되감는다는 것이 두 번째 미덕이다.

이 문서는 KL의 연산 단위·이득 계산·패스 구조와 그것을 실용 궤도에 올린 피두치아-마테이시스(FM) 변형을 다룬다. 균형 이분할이라는 문제 자체의 정식화와 난이도, 스펙트럴 완화 같은 다른 계열의 해법은 그래프 분할에, 다단계 파이프라인 전체와 구현 옵션은 METIS에, 라플라시안 고유벡터 쪽 이야기는 피들러 벡터에 있다.

2. 문제 설정과 D 값[편집]

정점 집합 $V$ ( $|V| = 2n$ )를 크기가 같은 두 조각 $A, B$ 로 나눈 상태에서 시작한다. 간선 가중치를 $c_{xy}$ ( $x,y$ 가 안 이어져 있으면 0)라 하면 목적함수는

T = \sum_{a \in A}\sum_{b \in B} c_{ab}

이다. KL의 모든 계산은 정점마다 하나씩 붙는 스칼라 위에서 돌아간다. $a \in A$ 에 대해 내부 비용과 외부 비용을

I_a = \sum_{x \in A} c_{ax}, \qquad E_a = \sum_{y \in B} c_{ay}, \qquad D_a = E_a - I_a

로 정의한다. $D_a$ 는 “ $a$ 를 혼자 반대편으로 보냈을 때 절단이 줄어드는 양”이다. 양수면 이 정점은 이미 남의 동네에 마음이 가 있는 셈이고, 음수면 자기 조각에 단단히 박혀 있다는 뜻이다. $B$ 의 정점에도 대칭적으로 정의한다.

이 $D$ 하나로 모든 것이 굴러간다는 게 KL의 계산적 핵심이다. 절단을 매번 처음부터 다시 세는 대신, $D$ 배열을 국소적으로 갱신하는 것만으로 임의의 교환 이득을 상수 시간에 조회할 수 있다.

3. 교환 이득과 패스[편집]

$a \in A$ 와 $b \in B$ 를 맞바꿨을 때 줄어드는 절단은 다음과 같다.

g_{ab} = D_a + D_b - 2\,c_{ab}

앞의 두 항은 둘을 따로따로 보냈을 때의 이득이고, 마지막 항이 보정이다. $a$ 와 $b$ 가 직접 이어져 있었다면 교환 전에는 그 간선이 잘려 있었지만 교환 후에도 여전히 잘려 있으므로, 각각의 $D$ 가 그 간선을 한 번씩 총 두 번 유리하게 세어 버린 것을 되돌려야 한다. 실제로 절단은 $T' = T - g_{ab}$ 가 된다.

교환을 실행한 뒤 남은 정점들의 $D$ 값은 다음처럼 갱신된다.

D'_x = D_x + 2c_{xa} - 2c_{xb}\ \ (x \in A\setminus\{a\}), \qquad D'_y = D_y + 2c_{yb} - 2c_{ya}\ \ (y \in B\setminus\{b\})

$a$ 의 이웃이었던 $x$ 입장에서는 이웃 하나가 건너편으로 갔으니 외부 비용이 $c_{xa}$ 만큼 늘고 내부 비용이 그만큼 줄어 $D$ 가 $2c_{xa}$ 오른다. 갱신 대상은 $a$ 나 $b$ 의 이웃뿐이므로 희소 그래프에서는 비용이 차수에 비례한다.

n=80 플랜티드 그래프에서 커니핸-린 한 패스를 스텝 단위로 돌린다. 이득이 음수인 교환도 일단 확정해 두 정점을 잠그고(누적이득 G_k 곡선이 0선 아래로 내려가는 구간), 패스 끝에 G_k 가 최대인 접두사 k* 까지만 남긴 뒤 나머지 교환을 되돌린다. 400시행 실측으로 무작위 초기 컷 377.8 → 수렴 166.9 이고, 확정된 교환의 13.0 %는 이득이 음수였다.

한 패스(pass)는 이렇게 진행된다.

모든 $D$ 값을 계산하고 전 정점의 잠금을 푼다.
잠기지 않은 쌍 중 $g_{ab}$ 가 최대인 $(a_i, b_i)$ 를 골라 가상으로 교환하고, 그 이득 $g_i$ 를 기록한 뒤 두 정점을 잠근다(lock).
나머지 정점의 $D$ 를 갱신하고 2로 돌아간다. 양쪽이 다 잠길 때까지 반복해 시퀀스 $g_1, g_2, \dots, g_n$ 을 만든다.
누적합 $G_m = \sum_{i \le m} g_i$ 가 최대가 되는 $m^\star$ 를 찾는다. $G_{m^\star} > 0$ 이면 앞의 $m^\star$ 개 교환만 실제로 반영하고 나머지는 전부 되돌린 뒤 1로 돌아가 새 패스를 시작한다. $G_{m^\star} \le 0$ 이면 종료.

잠금은 두 가지 일을 한다. 하나는 같은 정점이 왔다 갔다 하는 무한 진동을 막는 것이고, 다른 하나는 패스가 정확히 $n$ 번의 교환으로 끝나도록 길이를 못 박는 것이다. 잠금이 없으면 이 절차는 그냥 그리디 국소탐색이 되어 첫 번째 국소최적에서 멈춘다.

4. 되돌리기가 핵심이다[편집]

4단계가 KL을 KL로 만드는 부분이다. 당장 이득이 음수인 교환도 일단 저지르고 나중에 되감는다. 그리디였다면 $g_i < 0$ 이 되는 순간 멈췄겠지만, KL은 계속 밀고 나가 $g$ 시퀀스 전체를 만든 다음 “돌이켜 보니 여기까지가 제일 좋았다”는 지점으로 되돌아간다.

왜 이게 필요한가. 조각 경계에 정점 다섯 개짜리 덩어리가 걸쳐 있고, 다섯 개를 통째로 옮기면 절단이 줄지만 하나씩 옮기면 매번 늘어나는 배치를 생각해 보자. 그리디는 첫 정점에서 이미 손해를 보고 물러선다. KL은 다섯 번의 음수 이득을 감수하고 넘어간 뒤 여섯 번째에서 누적합이 양수로 뒤집히는 것을 발견한다. 즉 되돌리기는 깊이 $m$ 짜리 언덕을 한 번에 넘는 능력을 $O(n)$ 개의 후보 접두사를 훑는 값으로 사는 장치다. 담금질 모사나 타부 서치가 확률이나 금지 목록으로 국소최적을 탈출하는 것과 목적은 같고, 수단이 결정론적이라는 점만 다르다.

비용은 정직하다. 매 단계에서 $O(n^2)$ 개의 쌍을 전수조사하고 그걸 $n$ 번 반복하면 패스당 $O(n^3)$ 이다. 원 논문은 $D$ 값을 정렬해 두고 상계 가지치기로 후보를 잘라 $O(n^2 \log n)$ 을 보고했지만, 어느 쪽이든 정점 수 제곱 이상이라 정점 수만짜리 그래프에는 못 쓴다. 패스 자체는 대개 두어 번, 많아야 서너 번 만에 개선이 멈춘다.

5. 피두치아-마테이시스 — 단일 이동과 버킷[편집]

1982년 피두치아와 마테이시스(Fiduccia–Mattheyses, FM)가 KL을 실용 궤도에 올렸다.² 바뀐 것은 두 가지다.

첫째, 연산 단위를 쌍 교환에서 단일 정점 이동으로 바꿨다. 쌍을 고르려면 $O(n^2)$ 개 조합을 봐야 하지만 정점 하나를 고르는 것은 $O(n)$ 이다. 대신 균형이 저절로 유지되지 않으므로, 허용 불균형 범위를 명시적으로 두고 그 범위를 깨지 않는 이동 중 최대 이득짜리를 고른다. 균형이 공짜에서 제약으로 강등된 셈인데, 실무에서는 어차피 $\varepsilon$ 만큼의 불균형을 허용하므로 오히려 자연스럽다.

둘째, 이득을 정수 버킷에 담았다. 정점 하나의 이득은 그 정점에 걸린 가중치 합을 넘을 수 없으므로, 가중치가 정수이고 최대 차수(하이퍼그래프에서는 최대 핀 수)가 $p_{\max}$ 면 이득은 $[-p_{\max}, +p_{\max}]$ 안의 정수다. 그러면 이득 값마다 이중 연결 리스트를 하나씩 두는 버킷 배열과 최대 이득 포인터 하나로

최대 이득 정점 뽑기: $O(1)$
이동 후 이웃들의 버킷 재배치: 이웃 하나당 $O(1)$

이 되고, 한 패스의 총비용이 핀 수(간선 접속 수) 합에 선형이 된다. 정렬도 힙도 필요 없다는 게 이 자료구조의 매력이다.

셋째 — 사실 VLSI 쪽에서는 이게 제일 컸다 — 하이퍼그래프에 그대로 확장된다. 회로의 넷(net)은 소자 여러 개를 한꺼번에 묶으므로 간선이 아니라 하이퍼에지이고, 넷 하나가 잘렸는지는 “그 넷에 걸린 소자가 양쪽에 다 있는가”로 판정된다. FM은 넷마다 양쪽 소자 수만 세어 두면 이득 갱신이 국소적으로 끝나도록 설계돼 있다. FM이 그래프 분할이 아니라 회로 분할 학회에서 태어난 이유다.

KL의 골격 — 잠금, 음의 이득 허용, 최적 접두사 되감기 — 은 그대로 물려받았다. 그래서 문헌에서는 보통 둘을 묶어 KL/FM 계열이라 부른다.

세부 구현이 품질을 크게 흔든다는 것도 알려져 있다. 이득이 같은 정점이 여럿일 때 어느 것을 꺼내느냐(버킷 리스트를 LIFO로 쓰느냐 FIFO로 쓰느냐)가 결과에 유의미한 차이를 낳고, 경험적으로 LIFO가 낫다. 크리슈나무르티(1984)의 선견 이득(look-ahead gain)은 동점을 “지금 이득”이 아니라 “이 정점을 옮긴 뒤 따라올 이득”까지 보고 깨는 확장이다.

6. 다단계 분할의 세련화 단계로 살아남다[편집]

KL/FM만 단독으로 큰 그래프에 돌리면 결과가 신통치 않다. 이유는 구조적이다.

국소 탐색이다. 초기 분할이 나쁘면 결과도 나쁘다. 무작위 이분할에서 출발하면 정점 수가 커질수록 무작위와 별 차이 없는 절단으로 수렴한다.
한 번에 한 정점(또는 한 쌍)만 본다. “경계 전체를 통째로 반대편으로 옮겨야 좋아지는” 종류의 개선은 원리적으로 찾지 못한다. 되돌리기가 언덕을 넘게 해 주지만, 그 언덕은 어디까지나 한 정점씩 밟아 올라갈 수 있는 언덕이다.

이 한계를 정면으로 뚫은 것이 1990년대 중반의 다단계 기법이다. 그래프를 정점 수백 개가 될 때까지 뭉쳐 놓으면, 거친 레벨에서 초정점 하나를 옮기는 것이 원 그래프에서는 정점 수천 개를 한꺼번에 옮기는 것과 같아진다. KL/FM의 “한 번에 하나”라는 제약이 레벨을 바꾸는 것만으로 사라지는 셈이다. 다중격자법이 매끄러운 오차를 조대 격자에서 잡는 구조와 정확히 같고, 그래서 다단계 분할은 사실상 절단에 대한 멀티그리드다.

이 구조 안에서 KL/FM은 세련화(refinement) 단계를 맡는다. 조대 레벨에서 이미 좋은 분할을 잡아 뒀으니 세밀한 레벨에서는 국소 수선만 하면 되고, 게다가 이득이 0이 아닐 수 있는 정점은 어차피 경계에 있는 것들뿐이므로 경계 정점만 큐에 넣는 경계 FM이면 충분하다. 정련 비용이 그래프 크기가 아니라 경계 크기에 비례하게 되는 이 최적화가 METIS류 도구가 백만 정점을 몇 초에 처리하는 비결이다. Chaco, METIS, ParMETIS, Scotch, KaHIP — 이름은 다 다르지만 안쪽의 정련 루프는 전부 FM의 후손이다.

7. 한계와 변주[편집]

가중치와 다중 제약. 원 KL은 정점 가중치를 고려하지 않는다. 셀마다 계산량이 다른 실제 격자에서는 정점 가중치가 필수이고, 여러 종류의 부하를 동시에 맞추려면 가중치 벡터와 다중 제약 정련이 필요하다.
$k$ 조각. KL/FM은 본질적으로 2분할 도구다. $k$ 조각은 재귀 이분할로 만들거나, 정점의 이동 후보를 “인접한 다른 모든 조각”으로 확장한 k-way 정련을 쓴다. 후자가 요즘 기본값이다.
절단은 통신량의 대리지표일 뿐이다. 정점 하나가 이웃 셋을 다른 조각에 두면 잘린 간선은 셋이지만 실제로 보내는 데이터는 자기 값 하나다. 이 어긋남을 정확히 세려면 하이퍼그래프 분할이 필요하다 — 아이러니하게도 FM은 원래 하이퍼그래프 도구였는데, 병렬 수치해석 쪽으로 넘어오면서 그래프 버전만 널리 쓰이게 됐다.
결정론적이라 다양성이 없다. 같은 초기 분할에서 출발하면 같은 답이 나온다. 그래서 실무에서는 무작위 시드를 여러 개 굴려 제일 좋은 것을 취하며, 다단계 안에서는 초기 분할 단계가 그 다양성을 공급한다.
재분할에는 그대로 못 쓴다. 적응 격자 세분화처럼 매 스텝 부하가 바뀌는 문제에서는 절단뿐 아니라 데이터 이주 비용도 목적함수에 들어가야 한다. 이 지점부터는 부하 분산의 영역이다.

정리하면 KL은 혼자서는 평범하고 다단계 안에서는 대체 불가능한 알고리즘이다. 50년 넘게 살아남은 조합 최적화 휴리스틱이 흔치 않다는 점을 생각하면, “좋은 국소 개선 연산자 하나를 제대로 설계해 두면 나머지는 남이 알아서 조립해 준다”는 교훈으로 읽을 만하다.³

8. 관련 문서[편집]

Kernighan, B. W. & Lin, S. (1970). “An Efficient Heuristic Procedure for Partitioning Graphs”. Bell System Technical Journal, 49(2), 291–307. 참고로 이 커니핸이 그 커니핸이다 — awk의 K, The C Programming Language의 K&R, hello, world를 세상에 퍼뜨린 그 사람. 조합 최적화 논문 한 편이 커리어의 각주 취급을 받는 인생도 있다. ↩
Fiduccia, C. M. & Mattheyses, R. M. (1982). “A Linear-Time Heuristic for Improving Network Partitions”. 19th Design Automation Conference. 제목에 “선형 시간”이 박혀 있는데, 이건 문제를 푸는 데 선형이라는 뜻이 아니라 패스 하나가 선형이라는 뜻이다. 논문 제목만 보고 NP-난해 문제가 풀렸다고 오해하면 곤란하다. ↩
반대로 KL/FM을 다단계 없이 백만 정점 그래프에 바로 돌려 놓고 “분할기가 이상하다”고 말하는 경우가 아직도 있다. 이상한 건 분할기가 아니라 초기값이다. 좋은 국소 개선기는 좋은 출발점을 요구한다는 점에서 뉴턴-랩슨법과 성격이 같다. ↩