Page 27 -

문제인 게 분명한 최대 안정 집합 문제가 구간 교차 관계를 나타내는 그래프라면 다항식 시간으로
풀 수 있다는 뜻입니다. 즉, 다루는 문제가 NP 난해 문제라는 걸 알고 있더라도 실제로 주어진 입
력이 어떤 성질인지 잘 따져보면 효율적으로 풀 수 있습니다.

그림 18-1 구간 스케줄링 문제와 최대 안정 집합 문제의 대응

दп

최대 안정 집합 문제를 다항식 시간으로 풀 수 있는 그래프의 등급으로는 다음 두 가지가 대표적
입니다. 1
18
● 이분 그래프

● 트리 어려운 문제 대책

이분 그래프의 자세한 설명은 생략하지만, 이분 그래프의 최대 매칭 문제(16.5절)로 환원해서 다
2
항식 시간으로 풀 수 있는 건 알려져 있습니다. 트리는 이분 그래프이기도 하므로 다항식 시간으
로 풀 수 있는 건 분명하지만, 트리 특유의 구조를 활용해서 탐욕법(7장)으로 푸는 방법도 있습니

다(연습 문제 18.1). 게다가 각 꼭짓점에 가중치가 있는 경우를 생각해 본 다음의 가중 최대 안정
집합 문제도 동적 계획법(5장)으로 풀 수 있습니다. 여기서는 가중 최대 안정 집합 문제를 동적 계
획법에 기반하여 푸는 방법을 설명하겠습니다.

1 최대 안정 집합 문제가 다항식 시간으로 풀리는 그래프의 등급으로 이런 모두를 포함하는 완벽 그래프(perfact graph)라는 것도 알려져 있습
니다.
2 참고 문헌 [5] 네트워크 흐름을 참고하길 바랍니다.

383