ある問題がNP困難といった場合は, クラスNPに属する全ての問題以上に難しいことを意味します. より正確に述べるために, 二つの問題の難しさを比較する帰着と呼ばれる概念を解説します.

帰着

帰着とは, 二つの問題の困難性を比較する方法です. 端的に言えば, 問題1を高速に (多項式時間で) 解くアルゴリズムを使って問題2を高速に(多項式時間で)解けるとき, 問題2は問題1に帰着できるといいます.

例1. クリークと独立点集合

例2. 最大フロー問題と最大マッチング問題

例3. ハミルトンパス問題とハミルトン閉路問題

このように, 一方の問題1を解くアルゴリズムを使ってもう一方の問題2が解けるとき, 問題1は問題2以上に難しいとみなします.

カープ帰着とチューリング帰着

• 例1と例2で構成したアルゴリズムはどちらも, 問題2の入力が与えられたとき, その入力を変形して問題1の入力を構成し, その入力上で問題1を解くアルゴリズムを走らせ, その出力をそのまま答えとして返しています. このように, 解きたい問題の入力を変形して一方の問題の答えに合致するように変形させ, 一度だけアルゴリズムを呼び出しその答えをそのまま出力するというような帰着をカープ帰着 (Karp reduction) もしくは多対一帰着 (many-one reduction) といいます.

  <aside> ⚠️

  厳密にはカープ帰着の概念は判定問題間の帰着にのみ定義される概念であり, 一般に最適化問題同士の帰着には用いない用語です. しかし例2のように「最適値が$x$以上かどうか？」という判定問題を考えることによって帰着を構成できます.

  </aside>

  厳密にはカープ帰着とは以下のように定義されます:

  <aside>

  二つの判定問題 $\Pi_1$ と $\Pi_2$ を考える. 問題 $\Pi_2$ から問題 $\Pi_1$ へのカープ帰着とは, 以下の条件を満たす関数 $f$ である:

  • $\Pi_1$ の入力 $x$ が与えられたとき, $f(x)$ は$\Pi_2$の入力であり, この関数 $f$ は $x$ の長さに関して多項式時間で計算できる.

  • 任意の入力 $x$ に対し, $x$ の $\Pi_1$における答えがTrue である $\iff$$f(x)$ の $\Pi_2$ における答えがFalseである. </aside>

  • 要するに, 判定問題に対して一方の問題の入力をもう一方の問題の入力に等価に変形 (つまり, 変形の前後で答えのTrue/Falseが変化しない)する関数 $f$ をカープ帰着と言います.

  • 例1では入力$x$はグラフを表しており, $f(x)$= $x$ の補グラフとなります.

• 一方, 例3ではハミルトン閉路問題を解くために, ハミルトンパス問題を解くアルゴリズムを何度も走らせています. このように関数を何度も使って問題を解くような帰着をチューリング帰着 (Turing redeuction) といいます.

ハミルトン閉路からハミルトンパスへのカープ帰着

• 上記の例3で説明した帰着はチューリング帰着でしたが, 実はカープ帰着を構成することができます. つまり, ハミルトン閉路の入力として与えられるグラフ$G$を等価なハミルトンパス問題の入力に変換することができます.

• 入力のグラフを $G=(V,E)$ とします. 目標は$G$がハミルトン閉路を含むかどうかを判定することです. 以下に帰着で構成されるグラフ $f(G)$ を定義します:

  • 元のグラフの頂点 $u \in V$ を一つ固定します (例えば頂点$0$). この頂点に隣接している頂点の集合を $S$ とします.
  • 新たに三つの頂点 $u',x,x'$ を追加し, 以下のように辺を追加します:
    • $u'$ から全ての $S$ の頂点に辺を張る.
    • 辺$\{x,u\}$ と $\{x',u'\}$ を張る.
  • このようにして得られるグラフを$f(G)$と定義します.

  

  • このグラフ $f(G)$ は以下のようなPythonコードで実装でき, 確かに多項式時間アルゴリズムです.

    def f(N): #入力として隣接リストを受け取るとする
    	n = len(N)
    	u = 0 #uを頂点0とする
    	u2 = n #頂点u2を追加
    	x = n+1 #頂点xを追加
    	x2 = n+2 #頂点x'を追加
    	for i in range(3):
    		N.append([]) #追加した3頂点用の隣接リストを作成していく
    	for s in N[u]:
    		N[u2].append(s)
    	N[u2].append(x2)
    	N[x2].append(u2)
    	N[x].append(u)
    	N[u].append(x)
    	return N
    

• このように構成すると, $G$と$f(G)$に対するハミルトン閉路とハミルトンパスの有無が一致します.

<aside>

命題. 任意のグラフ $G$ に対して以下が成り立つ:

$$ \text{$G$がハミルトン閉路を持つ} \iff \text{$f(G)$がハミルトンパスを持つ}. $$

</aside>

• 証明 (概要)