트리폭

1. 개요

트리폭 Treewidth
정의	모든 트리 분해 중 (가장 큰 가방 크기 − 1)의 최솟값
같은 값	최적 소거 순서의 최대 차수 / 최소 현 확장의 최대 클리크 − 1
예	나무 1, 사이클 2, $K_n$ 은 $n-1$, $k\times k$ 격자 $k$
계산 복잡도	일반적으로 NP-난해 (1987), 고정 $k$ 면 선형 시간 (1996)
정립	로버트슨·시모어 그래프 마이너 연작 (1980년대)
쓰는 곳	확률 추론, 희소 소거, 텐서망 축약, 제약 충족

“이 그래프는 얼마나 나무에 가까운가?” 를 정수 하나로 답한다.

트리폭(treewidth)은 그래프를 나무 모양으로 배열한 정점 묶음(가방)으로 덮을 때, 가장 큰 가방을 얼마나 작게 만들 수 있는지를 재는 그래프 불변량이다. 나무의 트리폭은 1이고, 완전 그래프 $K_n$ 은 $n-1$ 로 최대다. 개념 자체는 1970년대 할린 등이 먼저 다뤘지만, 이 이름과 지금의 지위는 닐 로버트슨과 폴 시모어의 그래프 마이너 연작(1983~2004)에서 왔다.

시뮬레이션·수치 쪽에서 이 숫자가 중요한 이유는 하나다. 변수를 하나씩 지워 가는 정확 알고리즘의 비용이 트리폭에 지수적으로, 그래프 크기에는 선형으로 든다. 베이지안 네트워크 추론, 희소 행렬의 가우스 소거, 텐서망 축약, 제약 충족 문제가 전부 이 구조다. 접합 트리 알고리즘 문서가 “비용은 트리폭이 정한다”는 절에서 확률 추론 쪽 결론을 정리했으니, 이 문서는 정의·동치 특성화·손 계산 예·계산 복잡도와 다른 분야의 쓰임을 다룬다.

2. 정의 — 트리 분해

그래프 $G=(V,E)$ 의 트리 분해(tree decomposition)는 나무 $\mathcal T$ 와, 그 나무의 각 노드 $t$ 에 붙인 정점 부분집합 $B_t\subseteq V$ (가방, bag)의 모음으로 다음 세 조건을 만족한다.

1. 덮기: 모든 정점이 어떤 가방에 들어 있다.
2. 간선 덮기: 모든 간선 $\{u,v\}$ 에 대해 $u,v$ 를 함께 담은 가방이 있다.
3. 연속성: 정점 $v$ 를 담은 가방들은 $\mathcal T$ 에서 연결된 부분나무를 이룬다.

분해의 폭은 $\max_t\lvert B_t\rvert-1$ 이고, 트리폭 $\mathrm{tw}(G)$ 은 가능한 모든 트리 분해 중 최소 폭이다. “−1” 은 나무의 트리폭을 1로 맞추려는 관례다(간선마다 가방 하나 $\{u,v\}$ 를 두면 폭 1).

세 번째 조건이 핵심이다. 이 조건 덕분에 나무의 한 간선을 자르면 양쪽 가방에 공통으로 든 정점들이 원래 그래프의 분리 집합이 된다. 즉 트리 분해는 “작은 분리 집합으로 그래프를 재귀적으로 쪼개는 법”을 나무 한 장에 적어 둔 것이다.

3. 같은 숫자의 다른 얼굴

트리폭은 정의가 여러 개인데 모두 같은 값을 준다. 실무자에게 가장 쓸모 있는 건 두 번째다.

• 현 확장: $G$ 에 간선을 더해 현 그래프(길이 4 이상의 사이클마다 지름길이 있는 그래프) $H$ 를 만들 때, $\mathrm{tw}(G)=\min_H\omega(H)-1$. $\omega$ 는 최대 클리크 크기다.
• 소거 순서: 정점을 하나씩 지우면서 지울 때마다 그 이웃끼리를 모두 잇는다(채움, fill-in). 지울 때의 이웃 수의 최댓값을 그 순서의 폭이라 하면, 트리폭은 모든 순서 중 최소 폭이다. 이 과정이 바로 희소 행렬의 가우스 소거법에서 피벗을 하나 지울 때 생기는 채움과 똑같다.
• 게임: 경찰 여러 명이 헬리콥터로 정점 위에 내려앉고, 도둑은 경찰이 없는 경로를 따라 무한히 빠르게 움직이며 경찰의 착륙을 미리 본다. 도둑을 반드시 잡는 데 필요한 경찰 수가 $\mathrm{tw}+1$ 이다(시모어·토머스 1993). 같은 논문의 브램블(bramble) 쌍대성이 하한을 증명하는 표준 도구다.

3.1. 손으로 해 보기 — 3×3 격자

정점을 행 순서로 번호 매긴 $3\times3$ 격자를 1번부터 순서대로 지워 보자.

1 - 2 - 3
|   |   |
4 - 5 - 6
|   |   |
7 - 8 - 9

• 1 을 지움: 이웃 {2, 4}, 채움 2–4 추가. 폭 2.
• 2 를 지움: 이웃 {3, 4, 5}, 채움 3–4, 3–5. 폭 3.
• 3 을 지움: 이웃 {4, 5, 6}, 채움 4–6. 폭 3.
• 4 를 지움: 이웃 {5, 6, 7}, 채움 5–7, 6–7. 폭 3.
• 5 를 지움: 이웃 {6, 7, 8}, 채움 6–8. 폭 3.
• 6 을 지움: 이웃 {7, 8, 9}, 채움 7–9. 폭 3. 이후는 모두 3 이하.

최대 폭이 3 이고 채움 간선이 8개 생겼다. 각 단계의 “지운 정점 + 그 이웃”이 가방이 되어 $\{1,2,4\},\{2,3,4,5\},\{3,4,5,6\},\{4,5,6,7\},\cdots$ 가 사슬 모양의 트리 분해를 이룬다. 이 순서는 “격자를 한 줄씩 훑으며 지나간 줄과 다음 줄 사이의 경계 $k$ 개만 기억하는” 전략이고, $k\times k$ 격자에서 일반적으로 폭 $k$ 를 준다. 그리고 그게 최적이다. 전수 탐색(부분집합 동적 계획법)으로 확인하면 $3\times3$ 은 3, $4\times4$ 는 4 가 정확한 트리폭이다. 같은 방법으로 페테르센 그래프는 4, 6-사이클은 2, $K_5$ 는 4 가 나온다.

4. 계산하기 어렵다, 그런데 쓸 만하다

트리폭 계산은 NP-난해다(안보리·코르네일·프로스쿠로프스키 1987). 그런데 매개변수 $k$ 를 고정하면 “트리폭이 $k$ 이하인가”는 정점 수에 선형 시간으로 판정된다(보들랜더 1996). 다만 그 상수가 $k$ 에 대해 천문학적이라 실용 알고리즘은 아니다. 실전 도구는 셋으로 나뉜다.

• 휴리스틱 상한: 최소 차수(이웃이 가장 적은 정점부터), 최소 채움(지울 때 새 간선이 가장 적게 생기는 정점부터). 대개 꽤 좋지만 보장은 없다. 직접 구현해 보면 동률을 번호순으로 깰 때 $10\times10$ 격자에서 두 휴리스틱 모두 폭 13 을 내는데, 단순한 행 순서는 최적값 10 을 낸다. 동률 처리 하나로 30% 가 왔다 갔다 한다.
• 하한: 트리폭이 $k$ 인 그래프에는 반드시 차수가 $k$ 이하인 정점이 있으므로 퇴화도(degeneracy)가 하한이 된다. 마이너를 취해도 트리폭은 늘지 않으므로, 간선을 수축해 가며 최소 차수를 키우는 “마이너 최소 폭” 같은 더 센 하한도 있다.
• 정확 해법: 분기 한정, SAT 인코딩, 위의 부분집합 동적 계획법. 2016~2017년 PACE 챌린지가 트리폭을 과제로 걸면서 수천 정점 규모의 실그래프를 정확히 푸는 공개 해법들이 나왔다.

일단 폭 $w$ 의 트리 분해를 손에 넣으면, 많은 NP-난해 문제가 $O(c^{w}\cdot n)$ 꼴로 풀린다. 예컨대 최대 독립 집합은 가방마다 “이 가방의 정점 중 어느 부분집합을 고를지” $2^{w+1}$ 가지 표를 잎에서 뿌리로 올리며 합치면 된다. 쿠르셀 정리(1990)는 이걸 일반화해, 일계 논리에 정점·간선 집합에 대한 양화를 더한 단항 이차 논리(MSO)로 적을 수 있는 그래프 성질은 모두 트리폭이 유계인 그래프에서 선형 시간에 판정된다고 말한다. 3-색칠 가능성, 해밀턴 사이클 존재 등이 여기 든다(그래프 색칠).¹

5. 시뮬레이션과 계산에서 만나는 곳

희소 직접 해법. 대칭 양정치 행렬의 촐레스키 분해에서 소거 순서 = 피벗 순서이고, 각 단계 이웃 수 = 그 열의 비영 원소 수다. 그래서 최적 피벗 순서를 찾는 것은 트리폭(정확히는 채움 최소화와 프론트 크기 최소화) 문제와 같은 몸이다. 최소차수 순서화와 중첩절단이 각각 위의 최소 차수 휴리스틱과 “분리 집합으로 쪼개기”의 구현이다. $n$ 정점 평면 그래프는 크기 $O(\sqrt n)$ 의 분리 집합이 있으므로(립턴·타잔) 트리폭이 $O(\sqrt n)$ 이고, 2차원 격자 해석에서 중첩절단이 잘 듣는 이유다. $k\times k\times k$ 3차원 격자는 트리폭이 $\Theta(k^2)=\Theta(n^{2/3})$ 이라 프론트가 훨씬 커진다. 3차원 문제에서 직접 해법이 메모리부터 터지는 근본 원인이 이 지수 차이다.

확률 추론. 베이지안 네트워크·마르코프 무작위장의 정확 추론은 상태 수 $s$ 에 대해 $O(n\,s^{w+1})$ 이다. 이징 모형을 격자 위에서 정확히 풀기 어려운 이유도, 1차원 사슬은 전달 행렬로 쉽게 풀리는 이유도 트리폭(각각 $L$ 과 1)으로 한 줄에 설명된다.

텐서망과 양자 회로. 텐서 네트워크를 축약하는 비용은 축약 순서에 따라 천차만별인데, 마르코프·시(2008)는 양자 회로를 텐서망으로 보고 그 그래프의 트리폭에 지수적인 시간으로 고전 시뮬레이션할 수 있음을 보였다. 깊이가 얕거나 연결이 국소적인 회로가 고전 컴퓨터로 잘 흉내 내지는 이유이고, “양자 우위” 실험 회로를 설계할 때 트리폭을 키우는 방향으로 배선하는 이유이기도 하다.

제약 충족과 컴파일러. 제약 충족 문제의 제약 그래프 트리폭이 작으면 동적 계획법으로 다항 시간에 풀린다. 의외의 곳도 있다. 소루프(1998)는 goto 없이 짠 구조적 프로그램의 제어 흐름 그래프가 트리폭이 작다는 것(C 기준 6 이하)을 보이고 이를 레지스터 할당에 썼다. 사람이 짠 코드는 생각보다 나무 같다.²

6. 흔한 오해

• “희소하면 트리폭이 작다” — 아니다. 3차원 격자, 확장 그래프(expander)는 차수가 상수인데 트리폭이 $n$ 의 거듭제곱으로 자란다. 희소성은 간선 수의 이야기고, 트리폭은 분리 집합 크기의 이야기다.
• “트리폭만 알면 비용을 안다” — 실제 비용은 가장 큰 가방 하나가 아니라 가방 크기 분포 전체가 정한다. 희소 솔버 쪽에서는 그래서 트리폭 대신 채움 수와 총 연산 수를 따로 최소화한다.
• “휴리스틱이 준 폭 = 트리폭” — 휴리스틱은 상한일 뿐이다. 위 $10\times10$ 예처럼 30% 넘게 빗나갈 수 있다. 논문에 “트리폭 $w$” 라고 적을 때는 그 값이 정확값인지 상한인지 밝히는 것이 예의다.³

7. 관련 문서

• 접합 트리 알고리즘 · 베이지안 네트워크 · 이징 모형 · 텐서 네트워크
• 최소차수 순서화 · 중첩절단 · 촐레스키 분해 · 가우스 소거법 · 희소 직접 솔버
• 제약 충족 문제 · 그래프 색칠 · NP-완전 · SAT 풀이기
• 현 그래프 · 그래프 마이너 · 매개변수화 복잡도

8. Footnotes

1. “선형 시간”이라는 말에 혹하면 안 된다. 쿠르셀 정리가 만드는 오토마톤의 상수는 $w$ 에 대해 지수의 지수의 지수…로 탑을 쌓는다. 이론가들의 “선형”과 현생 개발자의 “선형”은 다른 단어다. ↩

2. 반대로 goto 를 마구 쓰면 트리폭이 얼마든지 커질 수 있다. 다익스트라가 goto 를 싫어한 이유에 그래프 이론적 근거가 하나 더 생긴 셈이다. ↩

3. 확률 그래프 모델 논문에서 “트리폭이 낮아서 정확 추론이 가능했다”는 문장 뒤에 휴리스틱 상한만 있는 경우가 꽤 있다. 결론이 틀리진 않는다(상한이 작으면 정확값도 작다). 반대 방향 주장, 즉 “트리폭이 커서 불가능했다”는 상한만으로는 성립하지 않는다. ↩