Minimum Vertex Cover: 최소 정점 덮개

Minimum Vertex Cover, 정점 덮개, vertex cover

정의

Vertex Cover 는 그래프의 모든 간선이 최소 한 정점을 포함하도록 하는 정점 집합. 최소 크기의 vertex cover 를 찾는 문제.

• 일반 그래프: NP-hard
• 이분 그래프: König’s Theorem 으로 최대 매칭 = 최소 정점 덮개, 이분 매칭 으로 다항 시간

König’s Theorem (이분 그래프)

|최소 vertex cover| = |최대 매칭|

증명: 최대 매칭 M 을 구한 뒤, 다음처럼 vertex cover 구성.

1. 왼쪽에서 M 에 안 걸린 정점 U 부터 alternating BFS
2. 방문된 왼쪽 정점 L’ 과 방문된 오른쪽 정점 R’ 관찰
3. Vertex cover = (왼쪽 \ L’) ∪ R’

응용

• 최대 독립 집합 = V \ 최소 vertex cover
• 최소 경로 덮개 (DAG)

참고

• 이분 매칭
• Maximum Flow