최소 정점 덮개

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

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: 극대 매칭. 세 줄이면 끝난다.

임의로 극대 매칭 $M$ 을 하나 잡는다(더 이상 간선을 추가할 수 없을 때까지 탐욕적으로).
$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. 관련 문서[편집]

실제로 FPT 교과서(다우니-펠로스, 사이크라 외)와 근사 알고리즘 교과서(바지라니, 윌리엄슨-슈모이스)가 전부 정점 덮개로 시작한다. 문제가 쉬워서가 아니라 모든 기법의 최소 작동 예제이기 때문이다. 새 기법을 개발했는데 정점 덮개에서 2를 못 깨면 대개 그 기법은 2를 못 깬다. ↩
오래된 자료에는 $O(1.28^k)$ 또는 $O(1.29^k)$ 로 적힌 것이 흔하다. 니더마이어-로스마니스의 $1.29^k$ 계열이 그 시절 수치이고, 첸-칸지-샤가 케이스 분석을 갈아 넣어 $1.2738$ 까지 내렸다. 소수점 셋째 자리를 놓고 논문이 나오는 분야라 인용할 때 연도를 같이 보는 편이 안전하다. ↩
“큰 그래프가 어려운 게 아니라 답이 큰 그래프가 어렵다”는 관찰이 매개변수 복잡도라는 분야 전체를 낳았다. 반대로 독립집합을 크기 $k$ 로 매개화하면 W[1]-완전이라 FPT가 아닐 것으로 믿어진다. 여집합 관계인 두 문제의 매개화된 복잡도가 갈리는 것은, 매개변수가 $k$ 와 $n-k$ 로 서로 다르기 때문이다. ↩