Algorithm Analysis: NP problems 3
알고리즘 관련 모든 글은 연세대학교 안형찬 교수님의 CSI_3108: Algorithm Analysis의 강의 내용과 자료입니다.
지난 시간에 살펴봤던 Vertex cover는 Set cover problem의 한 가지 예시입니다. 이번 글에서는 좀더 여러 상황에 적용해볼 수 있는 set cover 문제를 정의해보고 실제 사례를 살펴보겠습니다.
Set Cover problem
Problem 1 (Set Cover). Given a ground set U , a collection $S_1 , . . . , S m$ of subsets of $U$ , and a number $k$, does there exist a collection of at most $k$ of $S_1 , . . . , S m$ whose union is equal to $U$ ?
문제 자체는 쉽습니다. 우리에게 주어진 어떤 집합 $U$ 가 있고, 이 $U$ 의 부분집합들 중 최대 $k$ 를 선택해서 전체 집합 $U$ 의 원소들을 다 커버해야 하는 문제입니다.
앞선 글에서 살펴봤던 Vertex cover 문제의 관점에서 생각해보면, graph $G$ 의 vertex 하나하나가 subset $S_i$ 인 셈입니다. 그리고 이 vertex에 인접해있는 edge들이 바로 이 subset이 포함하고 있는 원소들입니다.
이렇듯 Vertex cover는 Set cover의 특수한 경우입니다. 따라서 Set cover 문제가 Vertex cover 보다 더 쉽지는 않을 것임을 유추할 수 있습니다. 이렇게 더 쉽지 않음을 보일 땐 어떻게 해야 하나요? 당연히 우리는 이제 polynomial-time reduction을 시킵니다. 어디서 어디로 polynomial-time reduction을 시켜야 할까요? Set cover가 Vertex cover 보다 더 쉽지는 않다는 것을 보이고 싶으니 Vertex cover에서 Set cover 로 reduction 시켜야 합니다. 그러므로 우리는 우선 Set cover를 1 스텝만에 바로 푸는 블랙박스가 있다고 가정합니다.
Theorem 3. Vertex Cover $\le_p$ Set Cover.
$Proof.$ 일단 graph $G=(V,E)$ 와 $k$ 가 Vertex Cover instance 로 주어져있고, Set cover 를 위한 블랙박스도 주어져있습니다. 우리는 주어진 Vertex cover instance를 Set cover instance 꼴로 변형시켜서 이 블랙박스를 이용해서 풀고 싶습니다. 위에서 말한대로 Set cover instance 를 만들어보겠습니다. Ground set $U$ 는 $G$ 의 edge 집합인 $E$ 로 잡습니다. 그리고는 각 vertex $i$ 는 자신에게 incident한 edge들을 원소로 갖는 subset $S_i$ 가 됩니다. 최대 vertex 개수에 대한 제약인 $k$ 는 그대로 Set Cover 에서 $k’$ 로 이용합니다. 이제 Set cover 를 푸는 블랙박스에 줄 input들이 다 정해졌으니 넣어서 답을 얻기만 하면 됩니다.
이제 다음으로는 yes instance 가 되는지 여부를 양방향으로 보이면 됩니다.
- 우선 주어진 Vertex cover 가 yes instance 라고 가정해보겠습니다. 그렇다면 최대 $k$ 의 vertex를 사용하는 Vertex cover $C$ 가 존재한다는 의미입니다. 그렇다면 우리는 변형시켜 얻은 set cover instance에서 주어진 vertex cover에 포함된 vertex 대로 subset 들을 고르면 됩니다. 그렇다면 모든 edge들이 vertex cover 에서 커버되었을테니, set cover instance 에서 edge들로 이루어진 ground set $U$ 도 커버가 될 것입니다. 따라서 Set cover instance 도 yes instance 가 됩니다.
- 이제는 반대방향으로 Set cover 가 yes instance 일 때를 살펴보겠습니다. $k’$ 개의 subset 들로 $U$ 를 커버하였으니, 그대로 Vertex cover 에서도 그 해당 subset 과 대응되는 vertex 들을 고르면 최대 $k(=k’)$ 개의 vertex를 사용하면서 전체 edge 들을 다 커버하였을 것입니다. 따라서 Vertex cover instance 도 yes instance 가 됩니다.
그러므로 Vertex cover 에서 Set cover 로의 polynomial-time reduction 은 옳습니다.
실제 사례 적용
실제로 시험에서는 Vertex cover 가 아니라 더 일반적인 형태의 Set cover 로 접근해야 하는 경우가 대부분입니다. 어떨 때 Set cover 가 적용되는지 살펴보기 위해 문제 하나를 가져와봤습니다.
Tour Guide problem
여러분이 여행가이드가 되었다고 생각하겠습니다. 여러분은 고객들을 위한 여행스케줄을 짜야 합니다. 고객들을 데려갈 수 있는 도시는 총 n개가 있습니다. 여러분은 이 n개 도시 중 몇 군데에 고객들을 데려가고 싶습니다. 다만 정해져있는 전체 이동시간 제한 $T$ 가 있습니다. 일단 각 도시에서 머무르는 시간은 무시하기로 하고, 도시와 도시 사이의 이동시간만 고려합니다. 그리고 도시 $i$ 에서 도시 $j$ 로 가는 이동시간이나 그 반대로 가는 이동시간은 동일하다고 간주합니다. 스케줄에서 시작하는 도시와 끝나는 도시는 여러분이 임의로 정할 수 있습니다.
추가적으로, 각 도시는 몇 개의 카테고리에 속합니다(카테고리는 총 $m$ 개 있습니다). 예를 들어 도시 $i$ 는 카테고리 $A$ 와 $D$ 에 속하는 식입니다. 따라서 카테고리 하나는 도시들을 원소로 갖는 부분집합입니다. 그런데 고객들은 단조로운 여행 스케줄을 바라지 않는다고 합니다. 그래서 $m$ 개의 각 카테고리에서 적어도 1개의 도시는 방문해야 한다고 합니다. 이런 제약을 안고 여러분은 고객들을 위한 여행 스케줄을 짜야 하는 문제입니다.
The Tour Guide problem is the following: given a set $S := {1, . . . , n}$ of cities, moving time $c : {s\choose 2} → N$, the maximum amount of moving time $T$ , and $m$ categories $ C_1 , . . . , C_m \subseteq S$, does there exist a path of cities such that the total moving time is at most $T$ and at least one city of each category is included?
풀이
우선 카테고리라는 부분집합 하나 안에는 도시들이 포함되어 있습니다. 그리고 우리는 각 카테고리에서 적어도 한 개의 도시는 방문하는 스케줄을 짜야 합니다. 다시 말해, 모든 카테고리가 커버되어야 한다는 의미가 됩니다. 그렇기 때문에 문제에서는 각 카테고리가 부분집합으로 주어져있지만, 실제로 문제를 풀 때는 카테고리는 ground set의 원소로 봐야 합니다.
정리
대개 무언가를 전체 다 커버해야 하는 문제의 경우에 Set cover 로 접근하면 좋습니다.
- Algorithm Analysis - NP Problems 1 SERIES 1/5
- Algorithm Analysis - NP Problems 2 SERIES 2/5
- Algorithm Analysis - NP Problems 3 ✓ SERIES 3/5
- Algorithm Analysis - NP Problems 4 SERIES 4/5
- Algorithm Analysis - NP Problems 5 SERIES 5/5