정점 덮개

그래프의 모든 변이 고른 꼭짓점 가운데 적어도 하나에 닿으면 그 꼭짓점 집합을 정점 덮개라 한다(꼭짓점 덮개라고도 한다). 「크기가 k 이하인 정점 덮개가 있는가」는 NP-완전이며 카프의 21개 문제 가운데 하나다. 아직 덮이지 않은 변을 골라 양 끝을 모두 넣는 일을 되풀이하면 최적 크기의 2배 이내인 덮개를 쉽게 얻는다. 이 2배를 본질적으로 줄일 수 있는지는 근사 알고리즘 분야의 미해결 문제다.