三维匹配问题

三維匹配（縮寫3DM）是六個經典NP完全問題之一，是經典穩定婚姻問題的推廣，婚姻問題是：有幾個未婚男子和幾個未婚女子以及一張列出雙方都表示願意結合在一起的一對對男子和女子的表格，問是否能安排幾對婚姻使得每個人都與自己願意接受的配偶結婚並且不出現重婚？

三維匹配。(a) 輸入 T。(b)–(c) 解。

在三維匹配問題中，可以用集合${\displaystyle W}$，${\displaystyle X}$和${\displaystyle Y}$對應於「三個」不同的性別，${\displaystyle M}$屬於${\displaystyle W*X*Y}$。用集合${\displaystyle M}$中的每一個三元組對應一對這三個成員都能接受的「三方婚姻」。普通的婚姻問題可以在多項式時間內解決，而3DM是NP完全的。

在數學學科的圖論中，三維匹配是二分圖匹配（也稱為二維匹配）推廣到三方超圖，它由超邊組成，每個超邊包含 3 個頂點（而不是普通圖中包含 2 個頂點的邊）。

三維匹配是最早證明為NP困難之一的問題。

定義

設 X、Y 和 Z 為有限集合，並設 T 為 X × Y × Z 的子集。也就是說，T 由三元組 (x, y, z) 組成，其中 x ∈ X，y ∈ Y，且 z ∈ Z。現在，如果以下條件成立，則 M ⊆ T 是一個三維匹配：對於任何兩個不同的三元組 (x₁, y₁, z₁) ∈ M 和 (x₂, y₂, z₂) ∈ M，我們有 x₁ ≠ x₂，y₁ ≠ y₂，且 z₁ ≠ z₂。

範例

右圖說明了三維匹配。集合 X 用紅色點標記，Y 用藍色點標記，Z 用綠色點標記。圖 (a) 顯示了集合 T（灰色區域）。圖 (b) 顯示了 |M| = 2 的三維匹配 M，圖 (c) 顯示了 |M| = 3 的三維匹配 M。

圖 (c) 中說明的匹配 M 是一個「最大三維匹配」，即它最大化 |M|。圖 (b)–(c) 中說明的匹配是「極大三維匹配」，即它們不能通過添加來自 T 的更多元素來擴展。

與二分圖匹配的比較

可以用完全類似的方式定義「二維匹配」。設 X 和 Y 為有限集合，並設 T 為 X × Y 的子集。現在，如果以下條件成立，則 M ⊆ T 是一個二維匹配：對於任何兩個不同的配對 (x₁, y₁) ∈ M 和 (x₂, y₂) ∈ M，我們有 x₁ ≠ x₂ 且 y₁ ≠ y₂。

在二維匹配的情況下，集合 T 可以解釋為二分圖 G = (X, Y, T) 中邊的集合；T 中的每條邊都將 X 中的一個頂點連接到 Y 中的一個頂點。然後，二維匹配是圖 G 中的一個匹配，即一組成對非相鄰的邊。

因此，三維匹配可以解釋為匹配對超圖的推廣：集合 X、Y 和 Z 包含頂點，T 的每個元素都是一條超邊，集合 M 由成對非相鄰的邊組成（沒有共同頂點的邊）。在二維匹配的情況下，我們有 Y = Z。

與Set packing 的比較

三維匹配是Set packing的一個特例：我們可以將 T 的每個元素 (x, y, z) 解釋為 X ∪ Y ∪ Z 的子集 {x, y, z}；那麼，三維匹配 M 由成對不相交的子集組成。

判定問題

在計算複雜性理論中，三維匹配是以下判定問題的名稱：給定一個集合 T 和一個整數 k，判斷是否存在一個三維匹配 M ⊆ T，使得 |M| ≥ k。

這個判定問題已知是NP完全的；是卡普的二十一個NP-完全問題之一。^[1] 即使在 k = |X| = |Y| = |Z| 且每個元素最多包含在 3 個集合中，也就是說，當我們想要一個 3-正則超圖中的完美匹配時，它也是 NP 完全的。^[1][2][3] 在這種情況下，三維匹配不僅是一個Set packing，而且還是一個精確覆蓋：集合 M 恰好覆蓋 X、Y 和 Z 的每個元素一次。^[4] 這個證明是通過從3SAT簡化而來的。給定一個 3SAT 實例，我們構造一個 3DM 實例如下：^[2][5]

對於每個變數 x_i，都有一個形狀像輪子的「變數 gadget」。它由重疊的三元組組成。三元組的數量是 x_i 在公式中出現次數的兩倍。恰好有兩種方法可以覆蓋 gadget 中的所有頂點：一種是選擇所有偶數索引的三元組，另一種是選擇所有奇數索引的三元組。這兩種方法分別對應於將 x_i 設定為「真」或「假」。 「真」選擇在每個奇數索引的三元組中恰好留下一個未覆蓋的頂點，而「假」選擇在每個偶數索引的三元組中恰好留下一個未覆蓋的頂點。

對於每個子句 x_i u x_j u x_k，都有一個形狀像玫瑰的「子句 gadget」。它由三個重疊的三元組組成，每個子句中的每個變數一個。它可以被覆蓋，若且唯若至少一個節點被變數 gadget 的選擇留下未覆蓋。

由於可能留下兩個或多個未覆蓋的節點，我們還需要一個「垃圾收集 gadget」。它的形狀像一朵更大的玫瑰。它由幾個重疊的三元組組成，每個變數 gadget 中可能留下的每個未覆蓋的頂點一個。此類 gadget 的數量被確定，以便只有在存在令人滿意的分配時才能完全覆蓋它們。

特例

存在用於求解稠密超圖中 3DM 的多項式時間演算法。^[6][7] 存在用於求解稠密超圖中的3DM的多主題的時間間隔演算法。 卡爾賓斯基, 魯欽斯基 & 希曼斯卡 (2009) harvtxt模板錯誤: 無指向目標: CITEREF卡爾賓斯基魯欽斯基希曼斯卡2009 (幫助) Keevash, Knox & Mycroft (2013)

優化問題

「最大三維匹配」是最大的三維匹配。在計算複雜性理論中，這也是以下優化問題的名稱：給定一個集合 T，找到一個最大化 |M| 的三維匹配 M ⊆ T。

由於上面描述的判定問題是 NP 完全的，因此這個優化問題是 NP困難 的，因此似乎沒有多項式時間演算法可以找到最大三維匹配。但是，存在有效率的多項式時間演算法可以找到最大二分圖匹配（最大二維匹配），例如霍普克羅夫特-卡普演算法。

近似演算法

對於三維匹配，有一個非常簡單的多項式時間 3-近似演算法：找到任何極大三維匹配。^[8] 就像極大匹配在最大匹配的 2 倍因子內一樣，^[9] 極大三維匹配在最大三維匹配的 3 倍因子內。

對於任何常數 ε > 0，都有一個用於三維匹配的多項式時間 (4/3 + ε)-近似演算法。^[10]

但是，獲得更好的近似因子可能很難：這個問題是 APX完全 的，也就是說，很難在某個常數內近似。^[11][12][8]

對於最大 3-d 匹配，很難實現 95/94 的近似因子，對於最大 4-d 匹配，很難實現 48/47 的近似因子。即使限制為每個元素恰好出現兩次的實例，這種困難仍然存在。^[13]

並行演算法

在大規模並行通訊模型中，存在各種用於 3-d 匹配的演算法。^[14]

參見

• NP完全問題列表
• 彩虹獨立集 – 可以從三維匹配簡化的一個問題。
• 數值三維匹配