3次元マッチング問題のNP完全性証明

はじめに

この記事では、完全3次元マッチング問題（3DM）がNP完全であることの証明を詳しく解説します。証明は3SATからの多項式時間還元 (Karp還元) により行います。

この記事は、Garey & Johnson著「Computers and Intractability: A Guide to the Theory of NP-Completeness」（1979）で示されている3次元マッチング問題のNP完全性証明について、その行間を補完する形で詳細な解説を試みたものです。証明の再構成にあたって細心の注意を払っていますが、正確性は保証できません。このため、研究や論文での引用には原著を参照することを強くお勧めします。

問題の定義

完全3次元マッチング問題（3DM）とは

完全3次元マッチング問題は以下のように定義されます:

入力:

等しい濃度を持つ3つの集合 $A, B, C$
$A \times B \times C$ の部分集合 $M$

問題:
$M$ の中から互いに素な部分集合を選び、$A, B, C$ の全ての要素を網羅できるかを判定する。

3SATとは

3SAT問題は以下のように定式化されます:

$n$個の変数 $x_1, x_2, \ldots, x_n \in U$
$m$個の節 $c_1, c_2, \ldots, c_m$ からなる論理式 $F$
各節は高々3つのリテラルの選言（OR）
この論理式が充足可能かどうかを判定する

NP完全性の証明

証明は以下の2ステップで行います:

$3DM \in NP$ の証明
$3SAT \leq_m 3DM$ の証明（多項式時間還元）

Step 1: 3DM ∈ NP の証明

入力されたマッチングが完全3次元マッチングになっているかどうかの検証は、以下の手順で多項式時間で行えます:

マッチングの要素が互いに素であることの確認
すべての要素がカバーされていることの確認

Step 2: 3SAT から 3DM への還元

以下の手順で3SATインスタンスを3DMインスタンスに変換します。

1. 基本構成要素の定義

まず、変数の真偽値割り当てを表現するためのマッチングを定義します:

$T_i^t = {(\bar{x}_i[j], a_i[j], b_i[j]) \mid 1 \leq j \leq m}$ // $x_i$がTrueの場合

$T_i^f = {(x_i[j], a_i[j+1], b_i[j]) \mid 1 \leq j < m} \cup {(x_i[m], a_i[1], b_i[m])}$ // $x_i$がFalseの場合

ここで、$a_i \in Y, b_i \in Z$ は真偽値割り当ての制御に使用する補助要素です。

2. 節に対応するマッチングの定義

各節$c_j$に対して以下のマッチングを定義します:

$C_j = {(x_i[j], s_1[j], s_2[j]) \mid x_i \in c_j} \cup {(\bar{x}_i[j], s_1[j], s_2[j]) \mid \bar{x}_i \in c_j}$

$s_1 \in Y, s_2 \in Z$ は節の真偽値割り当ての制御に使用する補助要素です。

3. バランス調整用のマッチング

要素数を調整するためのダミーマッチング$G$を以下のように定義します:

$G = {(x_i[j], g_1[k], g_2[k]), (\bar{x}_i[j], g_1[k], g_2[k]) \mid 1 \leq k \leq m(n-1), 1 \leq i \leq n, 1 \leq j \leq m}$

4. 最終的な集合の構成

これらを用いて、以下のように集合$X, Y, Z$とマッチングセットを構成します:

$X = {x_i[j], \bar{x}_i[j] \mid 1 \leq i \leq n, 1 \leq j \leq m}$
$Y = A \cup S_1 \cup G_1$
$Z = B \cup S_2 \cup G_2$

ここで:
$A = {a_i[j] \mid 1 \leq i \leq n, 1 \leq j \leq m}$
$B = {b_i[j] \mid 1 \leq i \leq n, 1 \leq j \leq m}$
$S_1 = {s_1[j] \mid 1 \leq j \leq m}$
$S_2 = {s_2[j] \mid 1 \leq j \leq m}$
$G_1 = {g_1[k] \mid 1 \leq k \leq m(n-1)}$
$G_2 = {g_2[k] \mid 1 \leq k \leq m(n-1)}$

$M = (\bigcup_{i=1}^n T_i) \cup (\bigcup_{j=1}^m C_j) \cup G$

還元の正当性

1. 集合の濃度が等しいことの確認

構成した集合$X, Y, Z$の濃度は以下のようになります:

$|X| = 2nm$
$|Y| = |A| + |S_1| + |G_1| = nm + m + m(n-1) = 2nm$
$|Z| = |B| + |S_2| + |G_2| = nm + m + m(n-1) = 2nm$

したがって、$|X| = |Y| = |Z| = 2nm$ となり、3つの集合の濃度は等しくなります。

2. 多項式時間での変換可能性

各集合のサイズは変数の数$n$と節の数$m$の多項式で表現されるため、この変換は多項式時間で実行可能です。

3. 充足可能性の保存（⇒方向）

3SATインスタンスが充足可能である場合、以下のように完全3次元マッチング$M'$を構成できます:

$M' = (\bigcup_{t(x_i)=T} T_i^t) \cup (\bigcup_{t(x_i)=F} T_i^f) \cup (\bigcup_{j=1}^m {(z_j[j], s_1[j], s_2[j])}) \cup G'$

ここで、$z_j$は$C_j$に含まれるリテラルのうち、割り当て$t$によってTrueとなるものです。3SATが充足可能であることからこのようなリテラルは必ず1つ以上存在します。

この$M'$が完全3次元マッチングであることを、以下の3つのステップで示します:

$M'$の要素が互いに素であることの証明

以下の点から、$M'$の要素が互いに素であることがわかります:
- $T_i^t$と$T_i^f$はそれぞれ異なる変数$x_i$について選ばれるため、互いに素です
- $T_i^t$内の要素は異なる$j$について$(\bar{x}_i[j], a_i[j], b_i[j])$の形を持ち、互いに素です
- $T_i^f$内の要素は$(x_i[j], a_i[j+1], b_i[j])$の形を持ち（ただし$j=m$のときは$a_i[1]$）、これらも互いに素です
- 各節$c_j$からは1つの要素$(z_j[j], s_1[j], s_2[j])$のみを選んでおり、異なる$j$について$s_1[j], s_2[j]$は互いに素です
- $G'$は未使用の$x_i[j], \bar{x}_i[j]$と新しい$g_1[k], g_2[k]$を使用するため、他の要素とは互いに素です
すべての要素がカバーされることの証明

以下の点から、すべての要素が正確に1回ずつカバーされることがわかります:

a. 各$x_i$について:
- $t(x_i) = T$のとき:
  - $T_i^t$により$\bar{x}_i[j]$がすべてカバーされる
  - 残りの要素のうち、$m$個は$(\bigcup_{j = 1}^{m} {(z_j[j], s_1[j], s_2[j])})$により
  - $m(n-1)$個は$G'$によりカバーされる
- $t(x_i) = F$のとき:
  - $T_i^f$により$x_i[j]$がすべてカバーされる
  - 残りの要素のうち、$m$個は$(\bigcup_{j = 1}^{m} {(z_j[j], s_1[j], s_2[j])})$により
  - $m(n-1)$個は$G'$によりカバーされる
b. その他の要素について:
- $A$の要素:$T_i^t$または$T_i^f$により、各$a_i[j]$がちょうど1回カバーされる
- $B$の要素:$T_i^t$または$T_i^f$により、各$b_i[j]$がちょうど1回カバーされる
- $S_1, S_2$の要素:各節$c_j$から選んだ1つの要素により、各$s_1[j], s_2[j]$がちょうど1回カバーされる
- $G_1, G_2$の要素:$G'$により、残りの要素とともにカバーされる
$G'$の具体的な構成

$G'$は以下の手順で構成できることを示します:
- 各$x_i, j$について、$t(x_i) = T$のとき$x_i[j]$が、$t(x_i) = F$のとき$\bar{x}_i[j]$が未使用
- 加えて、特定の節を真にするためのリテラルの1つが$z_j$として選ばれ、これが$m$個
- 残りの$m(n-1)$個を$G'$に割り当てる
- $g_1[k], g_2[k]$は$1 \leq k \leq m(n-1)$で定義され、十分な数がある
- したがって、未使用の要素をこれらの$g_1[k], g_2[k]$と組み合わせて$G'$を構成できる

以上の3点により、構成した$M'$が完全3次元マッチングとなることが示されました。

以下にこの変換の具体例を示します。

4. 充足可能性の保存（⇐方向）

完全3次元マッチングが存在する場合、$a_i$と$b_i$の組み合わせが$T_i^t$または$T_i^f$により一意に決定されるため、対応する変数$x_i$の真偽値割り当てが決定され、元の3SATインスタンスの充足可能性が導かれます。

結論

以上の証明により、以下が示されました:

$3DM \in NP$
$3SAT \leq_m 3DM$（多項式時間還元可能）

したがって、3DMはNP完全であることが証明できました。

参考文献

Garey, M. R., & Johnson, D. S. (1979). Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman.
Karp, R. M. (1972). Reducibility among Combinatorial Problems. In Complexity of Computer Computations (pp. 85-103).