巡回セールスマン問題

閉路そのものを証明書にすれば、多項式時間で確かめられるので HAM は NP に属する。有向の判定からの多項式時間還元を作る。要点：有向グラフ $D$ の各頂点 $v$ を道 $v^-\,v^0\,v^+$ に置き換え、辺 $u\to v$ を辺 $u^+v^-$ にする。$v^0$ の次数が $2$ なので、無向の Hamilton 閉路は各 $v$ の 3 頂点を続けて通るしかなく、向きがそろう。

$\alpha$-近似アルゴリズム $\mathcal{A}$ があるとして、HAM を多項式時間で判定する。頂点が $n\ge3$ 個のグラフ $G$（$n\le2$ なら Hamilton 閉路はない）に対し、$K:=\lceil\alpha n\rceil+1$ とおき、$G$ の辺には費用 $1$、$G$ の辺でない頂点の対には費用 $K$ を与える。$K$ は $n$ の 1 次式で抑えられるので、この入力は多項式時間で作れる。$\mathcal{A}$ の出力 $T$ がすべて $G$ の辺からなるかを確かめ、そうなら「Hamilton 閉路あり」と答える。
$G$ が Hamilton 閉路をもてば $\mathrm{OPT}=n$ なので $c(T)\le\alpha n< K$ であり、$T$ は費用 $K$ の辺を含まない。よって $T$ は $G$ の Hamilton 閉路で、答えは正しい。$G$ が Hamilton 閉路をもたなければ、どの巡回路も $G$ の辺でない対を含むので、答えは「なし」になり正しい。こうして HAM は P に属し、prop-tsp-ham と NP完全 の命題「還元の基本性質」の 4 により P $=$ NP である。$\square$

最適な巡回路から辺を 1 本除くと Hamilton 路になり、これは全域木である。費用は $0$ 以上なので、その費用は $\mathrm{OPT}$ 以下で、$c(\mathrm{MST})$ 以上である。$\square$

Euler閉路 の定理「Euler の定理」により $(V,M)$ には Euler 閉路 $(y_0,y_1,\dots,y_L=y_0)$ があり、これは多項式時間で求まる（WS11 p. 45）。この列で各頂点が初めて現れる順に $x_1=y_0,x_2,\dots,x_n$ と並べ、$T=\{x_1x_2,\dots,x_{n-1}x_n,x_nx_1\}$ とする。$x_i=y_{a_i}$（初めて現れる位置、$a_1=0< a_2< \dots< a_n$）とし、$a_{n+1}:=L$ とすると、三角不等式をくり返し使って
$$ c(x_ix_{i+1})\le\sum_{j=a_i+1}^{a_{i+1}}c(y_{j-1}y_j)\qquad(1\le i\le n,\ x_{n+1}:=x_1) $$
である。右辺の区間は互いに重ならず、合わせると Euler 閉路全体になるので、$c(T)\le c(M)$ である。$\square$

各辺を 2 本にすると各頂点の次数は偶数で、$T_0$ は連結なので lem-tsp-shortcut が使える。得られる巡回路 $T$ は $c(T)\le2c(T_0)\le2\,\mathrm{OPT}$ を満たす（lem-tsp-mst）。各段は多項式時間である。$\square$

次数の和 $2\lvert T_0\rvert$ は偶数なので $\lvert O\rvert$ は偶数で、$N$ はとれる。$T_0+N$ は連結で、$O$ の頂点の次数は $1$ 増え、ほかは変わらないので、すべて偶数である。よって巡回路 $T$ で $c(T)\le c(T_0)+c(N)$ となるものが得られる。
$c(N)\le\mathrm{OPT}/2$ を示す。$O=\emptyset$ なら明らか。そうでなければ、最適な巡回路を 1 周する順に $O$ の頂点を $o_1,\dots,o_{2k}$ と並べ、$o_{2k+1}:=o_1$ とする。巡回路は $o_i$ と $o_{i+1}$ を結ぶ $2k$ 本の互いに辺を共有しない部分の道に分かれ、三角不等式により $c(o_io_{i+1})$ はその部分の道の費用以下なので、$\sum_{i=1}^{2k}c(o_io_{i+1})\le\mathrm{OPT}$ である。$N_1=\{o_1o_2,o_3o_4,\dots,o_{2k-1}o_{2k}\}$ と $N_2=\{o_2o_3,\dots,o_{2k}o_1\}$ はどちらも $O$ の完全マッチングで（$k=1$ なら $N_1=N_2=\{o_1o_2\}$）、$c(N_1)+c(N_2)$ は上の和に等しい。よって $c(N)\le\min\{c(N_1),c(N_2)\}\le\mathrm{OPT}/2$ である。
lem-tsp-mst と合わせて $c(T)\le\mathrm{OPT}+\mathrm{OPT}/2$ である。$\square$

$\lvert S\rvert\ge2$ とする。$1$ から $S$ を通って $j$ で終わる道で、$j$ の直前の頂点を $i\in S\setminus\{j\}$ とすると、$i$ までの部分は $1$ から $S\setminus\{j\}$ を通って $i$ で終わる道で、費用は $C(S\setminus\{j\},i)$ 以上である。よって道の費用は右辺以上である。逆に、各 $i$ について $C(S\setminus\{j\},i)$ を実現する道に辺 $ij$ をつなぐと（$j$ はその道に現れない）、$S$ を通って $j$ で終わる道になるので、$C(S,j)$ は右辺以下である。どの巡回路も、頂点 $1$ から出て残りの頂点を 1 回ずつ通る道に、最後の頂点 $j$ から $1$ へ戻る辺を足したものとして書け、逆にそのような道と辺はどれも巡回路を作るので、最後の式が成り立つ。
組 $(S,j)$ は $(n-1)2^{n-2}$ 個以下で、それぞれ $n$ 個以下の候補の最小をとるので、全体は $O(n^22^n)$ である。$\square$