상위 문서: 알고리즘 설계와 분석
개요
Vertex Cover
Vertex Cover 문제는 아래와 같은 정의를 가진다.
입력: 그래프 [math]\displaystyle{ G=(V,E) }[/math], 정수 [math]\displaystyle{ k }[/math] 질문: 최대 [math]\displaystyle{ k }[/math]개의 정점만 선택해서 모든 간선이 적어도 하나의 선택된 정점에 닿도록 만들 수 있는가?
해당 문제는 3-SAT [math]\displaystyle{ \rightarrow }[/math] Vertex Cover reduction을 통해서 Vertex Cover가 NP-Complete임을 보일 수 있다. 이때 Vertex Cover의 complement는 Independent Set이다.