최소 정점 덮개

1. 개요

최소 정점 덮개 Minimum Vertex Cover
정의	모든 간선이 적어도 한 끝점을 갖도록 고른 최소 크기의 정점 집합
기호	덮개수 $\tau(G)$
지위	카프(1972)의 21개 NP-완전 문제 중 하나 (node cover)
근사	2-근사 두 가지 — 극대 매칭 · LP 반정수 반올림
근사 하한	$\sqrt{2}$ (Khot–Minzer–Safra 2018) · 유일게임 가정 하 $2-\varepsilon$
FPT	커널 $2k$ 정점 · 분지 $O(1.2738^k + kn)$
이분 그래프	쾨니그 정리 + 최대유량으로 다항시간 정확해
쌍대	여집합이 곧 최대 독립집합

최소 정점 덮개(minimum vertex cover)는 그래프의 모든 간선이 적어도 한쪽 끝점을 포함하도록 정점을 고를 때, 그 개수를 최소화하는 문제다. 덮개수를 $\tau(G)$로 쓴다. “모든 연결을 감시하려면 어느 지점에 감시자를 두어야 하는가”라는 형태로 어디에나 나타나며, 그 단순함 덕분에 NP-난해 문제 이론의 실험실 쥐 역할을 해 왔다.

이 문제 하나에 조합 최적화의 주요 도구가 전부 들러붙어 있다. 두 줄짜리 근사 알고리즘, 선형계획법 완화의 반정수성, 유일게임 가정 하의 정확한 근사 하한, 고정 매개변수 다루기 쉬움(FPT)의 표준 예제, 그리고 쾨니그 정리를 통한 이분 그래프의 다항시간 정확해까지. “이 도구가 정점 덮개에서 뭘 하는지”를 보면 그 도구를 이해한 것이라는 말이 나올 정도다.¹

한편 최대 독립집합과는 여집합 관계로 완전히 붙어 있다. $C$가 덮개인 것과 $V \setminus C$가 독립집합인 것이 동치이므로 갈라이 항등식 $\alpha(G) + \tau(G) = n$이 항상 성립하고, 두 문제의 정확한 답은 동시에 결정된다. 그런데도 근사 가능성은 극과 극이다 — 덮개엔 2-근사가 있고 독립집합엔 상수 근사가 없다.

2. 정식화

가중 버전까지 포함해 정수계획법으로 쓰면 이렇다.

$$\min \sum_{v \in V} w_v x_v \quad \text{s.t.} \quad x_u + x_v \ge 1 \ \ \forall\, uv \in E, \quad x_v \in \{0,1\}$$

제약이 간선마다 하나씩, 변수가 정점마다 하나씩인 극도로 단순한 구조다. 이 정식화가 정점 덮개를 집합 덮개(set cover)의 특수 케이스로 만들어 준다 — 각 간선이 덮여야 할 원소이고, 각 정점이 자기에게 붙은 간선들을 덮는 집합이다. 다만 “각 원소가 정확히 두 집합에만 속한다”는 제약이 붙은 매우 특수한 집합 덮개라, 일반 집합 덮개의 $\ln n$ 벽 대신 상수 근사가 가능하다.

3. 카프의 목록에 오른 경위

1972년 리처드 카프가 Reducibility Among Combinatorial Problems에서 21개 문제를 NP-완전으로 묶었을 때, 목록에는 클리크·독립집합(set packing)·node cover가 나란히 들어갔다. 셋이 여집합·여그래프 변환으로 서로 환원되므로 사실상 하나의 항목이 세 얼굴로 등재된 것이다.

환원 자체는 3-SAT에서 온다. 각 변수마다 $x$와 $\bar x$를 잇는 간선 하나(총 $n$개), 각 절마다 세 리터럴을 잇는 삼각형 하나(총 $m$개)를 두고 같은 리터럴끼리 연결하면, 크기 $n + 2m$의 덮개가 존재하는 것과 원래 논리식이 충족 가능한 것이 동치가 된다. 변수 간선에서는 반드시 하나, 삼각형에서는 반드시 둘을 골라야 하므로 예산이 정확히 꽉 차고, 남는 자유도가 곧 진리 배정이다. 학부 계산이론 수업에서 이 환원을 손으로 그려 보는 이유는 예산 계산이 이만큼 깔끔한 환원이 드물기 때문이다.

4. 2-근사 — 두 가지 방법

방법 1: 극대 매칭. 세 줄이면 끝난다.

1. 임의로 극대 매칭 $M$을 하나 잡는다(더 이상 간선을 추가할 수 없을 때까지 탐욕적으로).
2. $M$에 속한 간선의 양쪽 끝점을 전부 답으로 낸다.

덮개가 맞다는 것은 극대성에서 나온다. 어떤 간선이 두 끝점 모두 답 밖에 있다면 그 간선을 $M$에 넣을 수 있어 극대성에 모순이다. 근사비는 한 줄이다 — $M$의 간선들은 끝점을 공유하지 않으므로, 어떤 덮개든 각 간선마다 서로 다른 정점을 최소 하나씩 써야 한다. 따라서 $\mathrm{OPT} \ge |M|$이고 우리가 낸 답은 $2|M| \le 2\,\mathrm{OPT}$다.

여기서 등장하는 하계 $\nu(G) \le \tau(G)$가 바로 쾨니그 정리가 이분 그래프에서 등식으로 만드는 그 부등식이다. 2-근사의 손실분은 정확히 이 부등식의 간극이고, 홀수 사이클이 그 간극의 원인이다. 삼각형 $K_3$에서 $\nu = 1$, $\tau = 2$인 것이 최소 사례.

방법 2: LP 반올림. 위 정식화의 $x_v \in \{0,1\}$을 $x_v \ge 0$으로 풀면 선형계획법 완화가 된다. 네뮤하우저와 트로터(1975)가 보인 것은 이 LP가 반정수성(half-integrality)을 갖는다는 것 — 모든 꼭짓점 해의 좌표가 $\{0, \tfrac12, 1\}$에만 놓인다. 그러니 $x_v \ge \tfrac12$인 정점을 전부 채택하면 실행 가능하고 비용은 많아야 2배다. 가중 버전에서도 그대로 통하는 것이 이 방법의 장점이다.

가중 버전에는 원-쌍대(primal-dual) 관점의 2-근사도 있다. 바르-예후다와 이븐(1981)의 국소 비율(local ratio) 기법으로, 간선 $uv$를 골라 $\min(w_u, w_v)$만큼 양쪽 가중치를 동시에 깎고 0이 된 정점을 답에 넣는 것을 반복한다. LP를 실제로 풀지 않으면서 LP 쌍대를 암묵적으로 구성하는 방식이라 구현이 가볍다.

정수 격차는 정확히 2다. 완전그래프 $K_n$에서 모든 $x_v = \tfrac12$가 실행 가능해 LP 값이 $n/2$인데 정수 최적은 $n-1$이다. 비율이 $n \to \infty$에서 2로 간다. 따라서 이 LP 경계만 쓰는 어떤 알고리즘도 2보다 나을 수 없다. 절단평면법으로 홀수 사이클 부등식 같은 유효 부등식을 추가해야 격차가 줄어든다.

5. 2를 못 깨는 이유

40년 넘게 아무도 $2 - \varepsilon$ 근사를 만들지 못했고, 그 이유가 점점 정리로 굳어지고 있다.

• 디누르-사프라(2005). P $\ne$ NP 하에서 $10\sqrt{5} - 21 \approx 1.3606$보다 나은 근사가 불가능하다.
• 콧-민저-사프라(2018). 2-to-2 게임 정리를 증명하면서 하한이 $\sqrt{2} \approx 1.4142$로 올라갔다.
• 콧-레게브(2008). 유일 게임 추측을 가정하면 모든 $\varepsilon > 0$에 대해 $2 - \varepsilon$ 근사가 NP-난해다.

즉 유일게임 가정을 받아들이면 극대 매칭 세 줄이 이미 최적 알고리즘이라는 결론이 된다. 무조건적 하한과 조건부 하한 사이에 $1.41$ 대 $2.0$의 간극이 남아 있고, 이 간극을 메우는 것이 근사 복잡도 분야의 대표적 미해결 문제다.

6. 고정 매개변수 다루기 쉬움

“입력 크기 $n$에 대해 어렵다”와 “답의 크기 $k$에 대해 어렵다”는 다른 이야기다. 매개변수 복잡도의 관점에서 정점 덮개는 FPT의 간판 문제다. 목표는 $f(k) \cdot n^{O(1)}$ 형태의 알고리즘이고, 여기서 지수는 $n$이 아니라 $k$에만 붙는다.

분지. 아무 간선 $uv$를 잡으면 $u$ 아니면 $v$가 반드시 덮개에 있다. 두 갈래로 분지하며 $k$를 1씩 줄이면 $O(2^k \cdot n)$이 즉시 나온다. 차수가 큰 정점을 우선 처리하고(차수 $\ge 3$인 $v$에 대해 “$v$를 넣는다” 대 ”$N(v)$ 전체를 넣는다”로 분지), 차수 1·2 정점을 축소 규칙으로 지우고, 케이스 분석을 촘촘히 하면 밑이 계속 내려간다. 현재 최선은 첸-칸지-샤(2010)의 $O(1.2738^k + kn)$이다.² 지수시간가설(ETH) 하에서는 $2^{o(k)}$ 알고리즘이 불가능하므로, 남은 개선 여지는 밑을 깎는 것뿐이다.

커널화. 더 우아한 쪽은 전처리로 인스턴스 자체를 줄이는 것이다.

• 버스 커널. 차수가 $k$보다 큰 정점은 반드시 덮개에 들어간다(안 넣으면 그 이웃 $k+1$개를 전부 넣어야 하니까). 그런 정점을 전부 골라내고 $k$를 줄인 뒤, 남은 그래프의 정점 차수는 모두 $\le k$다. 크기 $k$의 덮개가 남은 간선을 전부 덮으려면 간선이 $k^2$개를 넘을 수 없으므로, 간선 수 $O(k^2)$짜리 커널이 나온다. 고립 정점을 지우면 정점 수도 $O(k^2)$.
• 네뮤하우저-트로터 커널. 위 LP 해를 다시 쓴다. $x_v > \tfrac12$인 정점은 어떤 최적해에 반드시 포함되고 $x_v < \tfrac12$인 정점은 배제해도 최적성을 잃지 않는다는 것이 NT 정리다. 남는 것은 $x_v = \tfrac12$인 정점들뿐이고 그 개수는 $2k$ 이하다. 정점 $2k$개짜리 커널이며, 반정수성이 근사에서 한 번, 커널화에서 또 한 번 일하는 셈이다. 왕관 축소(crown reduction)라는 조합적 방법으로도 같은 결과에 도달한다.

커널 크기에도 하한이 있다. 델과 판 멜케벡(2010)은 coNP $\subseteq$ NP/poly가 아닌 한 총 비트 수 $O(k^{2-\varepsilon})$짜리 커널이 존재하지 않음을 보였다. $2k$ 정점 커널의 간선 수가 $O(k^2)$이므로 위 결과는 본질적으로 최적이다.

실무적 의미는 분명하다. 정점 100만 개짜리 네트워크라도 답이 $k = 60$ 규모라면, 커널화 후 남는 것은 정점 120개짜리 그래프이고 거기서 분지한정을 돌리면 된다. 큰 그래프가 어려운 게 아니라 답이 큰 그래프가 어렵다.³

7. 이분 그래프 — 정확해가 공짜

이분 그래프에서는 쾨니그 정리에 의해 $\tau = \nu$이고, 최대 매칭에서 최소 덮개를 구성하는 절차까지 따라온다. 미포화 정점에서 교대 경로로 도달 가능한 집합 $Z$를 잡고 $C = (X \setminus Z) \cup (Y \cap Z)$를 취하면 된다.

네트워크 흐름 언어로 옮기면 더 직관적이다. 소스 $s$에서 $X$의 각 정점으로 용량 1, $Y$의 각 정점에서 싱크 $t$로 용량 1, 원래 간선은 용량 $\infty$인 망을 만든다. $\infty$ 간선은 절단에 못 들어가므로 최소 절단은 $s$쪽 또는 $t$쪽 단위 용량 간선들의 모음이고, 그 간선에 대응하는 정점 집합이 곧 최소 정점 덮개다. 최대유량-최소절단 정리가 쾨니그 정리를 그대로 뱉는다. 가중 버전도 용량을 $w_v$로 바꾸면 그대로 작동해서, 가중 이분 정점 덮개도 최소 절단 한 번이다.

복잡도는 이분 매칭의 홉크로프트-카프로 $O(E\sqrt{V})$. 일반 그래프였다면 NP-난해였을 문제가 이분성 하나로 다항시간이 되고, 이 대비가 전체 단모듈성의 이야기와 정확히 맞물린다 — 이분 그래프의 접속행렬은 완전 단모듈이라 위 LP의 꼭짓점이 애초에 정수점이다. 홀수 사이클이 있으면 단모듈성이 깨지고 $\tfrac12$짜리 꼭짓점이 생긴다. 반정수성은 단모듈성이 실패한 흔적인 셈.

8. 어디에 쓰이나

• 모니터링·감시 배치. 링크마다 감시자가 필요한 네트워크에서 최소 노드 배치가 그대로 정점 덮개다. 실무 규모에서는 커널화 후 정확히 푸는 것이 보통이며, 근사비 2를 감수할 이유가 별로 없다.
• 충돌 해소. 서로 양립 불가능한 항목 쌍을 간선으로 놓고 최소한만 버려서 나머지를 살리는 문제. 버릴 집합이 덮개, 살릴 집합이 독립집합이다. 계산생물학의 서열 정렬 필터링, 데이터 정제의 중복 제거가 이 형태다.
• 희소행렬 구조 해석. 희소행렬의 행·열 이분 그래프에서 매칭과 덮개가 덜마주-멘델존 분해를 만든다. 구조적 특이성이 어디서 오는지 지목하는 정점 집합이 곧 여기서 나오는 덮개다.
• 문제 하한의 원천. 새 문제가 NP-난해임을 보일 때 가장 자주 쓰이는 출발점 중 하나다. 정점 덮개에서 환원하면 근사 하한까지 유일게임 가정 하에 함께 딸려 오는 경우가 많다.

9. 관련 문서

• 최대 독립집합 · 쾨니그 정리 · 이분 매칭 · 홀의 결혼정리
• 근사 알고리즘 · 분지한정법 · 조합 최적화
• 선형계획법 · 정수계획법 · 쌍대성 · 전체 단모듈성 · 절단평면법
• 네트워크 흐름 · 희소행렬
• NP-완전 · 매개변수 복잡도 · 유일 게임 추측
• 안정 결혼 문제 · 중국 우편배달부 문제

10. Footnotes

1. 실제로 FPT 교과서(다우니-펠로스, 사이크라 외)와 근사 알고리즘 교과서(바지라니, 윌리엄슨-슈모이스)가 전부 정점 덮개로 시작한다. 문제가 쉬워서가 아니라 모든 기법의 최소 작동 예제이기 때문이다. 새 기법을 개발했는데 정점 덮개에서 2를 못 깨면 대개 그 기법은 2를 못 깬다. ↩

2. 오래된 자료에는 $O(1.28^k)$ 또는 $O(1.29^k)$로 적힌 것이 흔하다. 니더마이어-로스마니스의 $1.29^k$ 계열이 그 시절 수치이고, 첸-칸지-샤가 케이스 분석을 갈아 넣어 $1.2738$까지 내렸다. 소수점 셋째 자리를 놓고 논문이 나오는 분야라 인용할 때 연도를 같이 보는 편이 안전하다. ↩

3. “큰 그래프가 어려운 게 아니라 답이 큰 그래프가 어렵다”는 관찰이 매개변수 복잡도라는 분야 전체를 낳았다. 반대로 독립집합을 크기 $k$로 매개화하면 W[1]-완전이라 FPT가 아닐 것으로 믿어진다. 여집합 관계인 두 문제의 매개화된 복잡도가 갈리는 것은, 매개변수가 $k$와 $n-k$로 서로 다르기 때문이다. ↩