-
A 1.5-Approximation for s-t Path TSP
이 글에서는 cost function이 metric인 경우에 대해서만 논의한다. 1. Introduction 외판원 문제(Traveling Salesman Problem)와 s-t 경로 외판원 문제(s-t path TSP)는 다음과 같이 정의된다. Traveling Salesman Problem. 완전 그래프 $G = (V, E)$ 와 간선 집합 $E$ 상의 metric cost function $c$가 있을 때, $G$의 모든 정점을 순회하고 돌아오는 최소 cost의 cycle을 구하여라. s-t Path Traveling Salesman Problem. 완전 그래프 $G = (V, E)$ 와 그 상의 두 정점 $s$, $t$ 및 간선 집합 $E$ 상의...
-
#P-완전성, 그리고 완전 매칭의 개수
이 글은 튜링 기계와 NP-complete에 대한 기본 배경지식을 전제로 합니다. 서론 이분 그래프가 주어졌을 때 최대 매칭을 구하는 문제는 알고리즘 문제 풀이에서 잘 알려져 있습니다. 심지어 일반적인 그래프가 주어져도 최대 매칭을 다항 시간에 구할 수 있습니다. 그러므로 완전 매칭이 존재하는지도 같은 방법으로 구할 수 있습니다. 하지만 완전 매칭의 개수를 구하라고 하면 어떻게 될까요? 카운팅 문제와 #P-완전 NP-완전성을 이야기할 때는 문제가 결정 문제로 한정됩니다. 예를 들어 최대 클릭 문제는 “가장 큰 클릭은 무엇인가?”가 아니라 “크기가 $k$...
-
Karp의 21대 NP-완전 문제
Richard Karp는 알고리즘의 선두를 이끈 인물 중 한 명입니다. Problem solving을 하는 사람들에게는 Edmonds-Karp 최대 유량, Hopcroft-Karp 이분 매칭, Rabin-Karp 부분문자열 탐색 등으로 잘 알려져 있는데, 이 분의 업적으로 NP-완전성을 빼놓을 수 없습니다. 배경 지식 P, NP, 다항 시간 환원, 그리고 NP-완전 문제에 대해서는 koosaga님의 글 계산 복잡도 위계와 불리언 식의 “QBF 문제” 직전까지를 참조해 주시기 바랍니다. NP-완전 문제 1971년, Stephen Cook은 The complexity of theorem proving procedures 논문에서 “비결정적 튜링 기계로 다항 시간에 결정할...