[CM301] 15. NP-hard: 최적화 문제 II (Optimization problem II)

 이전 절에서는 최댓값 최적화 문제에 대해 다뤄보았는데, 이번 절에서는 최솟값 최적화 문제들에 대해 다뤄보겠습니다.

정점 커버 (Vertex Cover)

 어떤 그래프 $G=(V, E)$에 속한 점들의 집합 $V’ \subseteq V$에 대해 $G$의 모든 선이 $V’$의 점들 중 하나를 지난다면, $V’$를 정점 커버^{Vertex Cover}라고 부릅니다.

 임의의 그래프가 주어졌을 때, 가장 적은 수의 정점 커버를 찾는 문제를 정점 커버 문제^Vertex-cover라고 하겠습니다.

결정 문제

  이 최적화 문제는 다음과 같은 결정 문제로 바꿀 수 있습니다.

DEC(Vertex-Cover): 주어진 그래프 $G=(V, E)$에서 점의 개수가 $k$ 이하인 정점 커버가 존재하는가?

 이 문제는 NP입니다. 점의 개수가 $k$ 이하인 점들의 집합을 준다면, 정말로 그래프의 모든 선들이 그 점들 중 하나를 지나는지는 다항 시간 안에 쉽게 확인할 수 있기 때문입니다.

NP-hard임을 보이기

  이 결정문제가 NP-hard임을 보이기 위해, NP-hard 였던 클리크 결정 문제를 정점 커버 결정 문제로 환원시켜 보겠습니다.

\[\text{DEC}(\text{Clique}) \leq_p \text{DEC}(\text{Vertex-Cover}) \; ?\]

 클리크는 하위 그래프에서도 완전 그래프, 즉 모든 점들이 모두에 대해 연결된 그래프의 점들을 뜻합니다. 그렇다면 최소 개수의 정점 커버는 클리크에 속한 점 중 일부 + 클리크를 지나지 않는 선과 연결된 점 중 일부 와 같은 형태를 가지게 될 것입니다. 이 실마리를 통해 클리크 문제를 정점 커버 문제로 바꿀 수 있을지도 모릅니다…

 그래프 $G=(V, E)$가 주어졌을 때, 그 그래프의 선을 반전시킨 상보적인 그래프 $\bar{G}=(V,\bar{E})$를 생각해봅시다. 이 그래프는 $G$에서 연결된 점들은 연결되어 있지 않고, 반대로 연결되지 않았던 점들은 연결되어 있습니다.

 $V_v \subseteq V$를 크기 $k$인 $\bar{G}$의 정점 커버라고 합시다.

 그렇다면 $\bar{G}$의 모든 선 $(u, v) \in \bar{E}$에 대해 $u$나 $v$ 둘 중 적어도 하나는 정점 커버에 속한 점이 됩니다.

\[(u, v) \in \bar{E} \quad \rightarrow \quad u \in V_v \; \text{or} \; v \in V_v\]

 그런데 이게 반대로 생각하면, $u$와 $v$ 둘 다 정점 커버에 속하지 않을 때는 $(u, v)$는 $G$의 선 $E$에 속하게 된다는 말이 됩니다.

\[u, v \in V-V_v \quad \rightarrow \quad (u, v) \in E\]

 $V-V_v$에 속한 모든 점들에 대해 연결된 선이 $E$에 포함되므로, 정의에 의해 $V-V_v$는 $G$의 클리크라고 할 수 있으며, 그 크기는 $|V| - |V_v| = |V| - k$개가 됩니다. 따라서, 그래프 $G$에서 점 k개의 클리크를 찾는 문제는 그래프 $\bar{G}$에서 점 $|V|-k$개의 정점 커버를 찾는 문제로 환원될 수 있습니다.

  그래프 $G$에서부터 $\bar{G}$를 이끌어내는 과정은 다항 시간이 소요되며, 클리크 문제는 NP-hard입니다. 따라서, DEC(Vertex-Cover)는 NP-hard입니다.

결론

 결정문제 DEC(Vertex-Cover)은 NP이고 NP-hard이므로 NP-complete입니다. 따라서, 최적화 문제 Vertex-Cover는 NP-hard, 즉 어렵습니다.

해밀토니안 (Hamiltonian)

 어떤 그래프의 모든 점들을 한 번만 방문하는 회로를 해밀턴 회로^{Hamiltonian Cycle}라고 합니다. 그리고 해밀턴 회로를 가지는 그래프는 해밀토니안^Hamiltonian이라고 합니다. 주어진 그래프가 해밀토니안인지 판별하는 문제는 해밀토니안 회로 문제^HAM라고 합니다.

 네, 이 문제는 최적화가 아닌, 존재 여부를 판단하는 결정 문제입니다. 그럼에도 여기서 소개하는 것은, 마지막으로 소개할 최적화 문제에서 사용하기 위함입니다. 이 문제 또한 어떻게 어렵다고 말할 수 있는지 살펴봅시다.

 이 문제는 NP입니다. 특정 회로가 주어진다면, 정말로 그 회로가 모든 점을 한 번만 지나게 되는지는 다항 시간 안에 쉽게 확인할 수 있기 때문입니다.

NP-hard임을 보이기

  이 결정문제가 NP-hard임을 보이기 위해, NP-hard 였던 정점 커버 결정 문제를 해밀토니안 회로 문제로 환원시켜 보겠습니다.

\[\text{DEC}(\text{Vertex-Cover}) \leq_p \text{HAM} \; ?\]

 역시 크기 $k$의 정점 커버를 가지는 그래프 $G$를 새로운 그래프 $G’$로 변환해줘야 하겠죠? 이 $G’$는 $G$가 크기 $k$의 정점 커버를 가질 때만 해밀턴 회로를 가지도록 만들어줘야 합니다.

 이를 위해서 에지 가젯^{Edge Gadget}이라는, 살짝 복잡한 개념을 사용하겠습니다. 이제부터 $G$의 두 점을 잇는 선 $(u, v) \in E$를 이런 모양의 가젯으로 바꾸어줄 것입니다.

 지금은 어쩌다 이런 모양이 되어버린 것인지 전혀 감이 오지 않을겁니다… 우선 이 구조에서 가능한 해밀턴 경로는 세 가지 뿐이라는 것에 주목합시다.

 앞서 주어진 그래프에서는 정점 커버를 찾는 문제를 풀어야 했습니다. 그러니 하나의 선 $(u,v)$에서 점을 선택할 수 있는 경우는 크게 세 가지가 있겠죠.

 가젯 하나에서 해밀턴 경로가 나오는 경우 세 가지, 그래프 선 하나에서 정점 커버가 선택되는 경우 세 가지, 딱 맞아 떨어지지 않나요? 이 가젯은 하나의 선에 대해 정점 커버가 선택될 수 있는 경우를 해밀턴 경로가 이뤄지는 방식으로 대응할 수 있습니다!

 그래프는 각 선이 독립적으로 존재하지 않고 같은 점을 공유하며 연결되어 있습니다. 그러니 변환한 가젯도 같은 점에 해당하는 부분을 연결하여 정점 체인^{Vertex Chain}을 만들어주어야 합니다.

 하지만 이렇게 하면 그래프 $G$가 $k$개의 정점 커버를 가질때만 $G’$가 해밀턴 회로를 가지도록 강제할 수 없습니다. 따라서 모든 정점 체인이 공유하는 정점 $k$개를 추가하여 $k$개의 정점 체인이 이 점들을 지날 수 있도록 만들어줍니다. 해밀턴 경로의 특성상 한 번 지나간 정점 체인은 다시 지나갈 수 없으니, $k$개의 공유 정점을 지나려면 서로 다른 정점 체인 $k$개를 지날 수 밖에 없는 것입니다.

 간단한 예시를 들자면, $k=2$인 정점 커버를 찾는 문제는 아래와 같은 해밀토니안 문제로 바꿀 수 있게 됩니다.

 따라서, 그래프 $G$에서 점 k개의 정점 커버를 찾는 문제는 그래프 $G’$에서 해밀턴 회로를 찾는 문제로 환원될 수 있습니다.

  그래프 $G$에서부터 $G’$를 이끌어내는 과정은 다항 시간이 소요되며, 정점 커버 문제는 NP-hard입니다. 따라서, HAM은 NP-hard입니다.

결론

 결정문제 HAM은 NP이고 NP-hard이므로 NP-complete입니다. 따라서, 해밀토니안 회로 문제는 어렵습니다.

순회 세일즈맨 문제 (TSP)

 자, 드디어 마지막 문제에 도달했습니다. 바로, 동적 계획법 II 절에서 보았던 순회 세일즈맨 문제입니다.

 모든 점이 서로 가중치로 연결된 완전 그래프가 있을 때, 가중치 합을 최소로 하는 해밀턴 회로를 구하는 문제를 순회 세일즈맨 문제(Traveling Salesmen Problem, TSP)라고 합니다. 앞서 우리는 이 문제를 동적 계획법으로 풀 때 $O(n^2\;2^n)$의 시간이 걸림을 알아 보았는데, 이제는 좀 더 엄밀하게 이 문제가 어려움을 보이려고 합니다.

결정 문제

  이 최적화 문제는 다음과 같은 결정 문제로 바꿀 수 있습니다.

DEC(TSP): 주어진 그래프 $G=(V, E)$에서 가중치 합이 k 이하인 해밀턴 회로가 존재하는가?

 이 문제는 NP입니다. 해밀턴 회로가 주어진다면, 정말로 그 회로의 가중치 합이 k 이하인지는 다항 시간 안에 쉽게 확인할 수 있기 때문입니다.

NP-hard임을 보이기

  이 결정문제가 NP-hard임을 보이기 위해, 앞서 말했던대로 해밀토니안 회로 문제를 사용해볼 것입니다. 해밀토니안 회로 문제를 순회 세일즈맨 문제로 환원시켜 봅시다.

\[\text{HAM} \leq_p \text{DEC}(\text{TSP}) \; ?\]

 TSP는 완전 그래프 문제이기 때문에, 해밀토니안 회로 문제의 그래프 $G$도 완전 그래프 $G’$으로 바꿔줄 필요가 있습니다. 원래 있던 선과 없던 선은 가중치의 크기로 구분하면됩니다. 원래 있던 선은 가중치를 0으로, 새로 생긴 선은 가중치를 1로 두면 되죠.

\[\text{weight}(u, v) = \begin{cases} 0 & (u, v) \in E \\ 1 & (u, v) \notin E \end{cases}\]

 나머지는 간단합니다. $G’$이 비용 0 이하인 TSP 회로를 그릴 수 있다면, 해밀턴 회로 또한 그릴 수 있게 됩니다. 모든 점들을 한 번만 방문하는데다, 비용이 0 이하가 되기 위해서는 가중치 1인 선은 지나지 않을테니까요.

 따라서, 그래프 $G$에서 점 해밀턴 회로를 찾는 문제는 그래프 $G’$에서 비용 0 이하인 TSP 경로를 찾는 문제로 환원될 수 있습니다.

  그래프 $G$에서부터 $G’$를 이끌어내는 과정은 다항 시간이 소요되며, 해밀토니안 회로 문제는 NP-hard입니다. 따라서, DEC(TSP)는 NP-hard입니다.

결론

 결정문제 DEC(TSP)는 NP이고 NP-hard이므로 NP-complete입니다. 따라서, 최적화 문제 TSP는 NP-hard입니다. 이것으로 우리는 지수 시간이 걸리던 TSP 문제가 실로 어렵다는 것을 엄밀하게 증명해내었습니다!