Independent Set

상위 문서: 알고리즘 설계와 분석

개요

Independent Set 문제는 아래와 같은 정의를 가진다.

입력: 그래프 $G=(V,E)$, 정수 $j$
질문: 서로 연결되지 않은 $j$개의 정점을 포함하는 집합이 존재하는가?

해당 문제는 Independent Set의 complement(여집합)가 Vertex Cover라는 사실을 이용하여 NP-Complete임을 증명할 수 있다.