3次元マッチング

数学の分野であるグラフ理論において、3 次元マッチングは、 2 部マッチング(2 次元マッチングとも呼ばれる) を 3 部ハイパーグラフに一般化したものです。3 部ハイパーグラフは、(通常のグラフでは 2 つの頂点を含むエッジではなく) それぞれが 3 つの頂点を含むハイパーエッジで構成されます。

3 次元マッチングは、3DMと略されることが多く、よく知られた計算問題の名前でもあります。つまり、与えられたハイパーグラフ内で最大の 3 次元マッチングを見つけることです。3DM は、NP 困難であることが証明された最初の問題の 1 つです。

X、Y、Z を有限集合とし、T をX  ×  Y  ×  Zのサブセットとします。つまり、T は、 x  ∈  X、y  ∈  Y、z  ∈  Zとなる三つ組 ( x、  y、  z )で構成されます。ここで、 M  ⊆  T は、次の条件が成立する場合、3次元マッチングです。任意の 2 つの異なる三つ組 ( x ₁、  y ₁、  z ₁ ) ∈  Mおよび ( x ₂、  y ₂、  z ₂ ) ∈  Mについて、 x ₁  ≠  x ₂、y ₁  ≠  y ₂、z ₁  ≠  z ₂が成立します。

右の図は 3 次元マッチングを示しています。集合Xは赤い点、Yは青い点、Z は緑の点でマークされています。図 (a) は集合T (灰色の領域) を示しています。図 (b) は| M | = 2 の3 次元マッチングMを示し、図 (c) は| M | = 3 の3 次元マッチングM を示しています。

図(c)に示すマッチングMは最大3次元マッチングであり、| M |を最大化します。図(b)～(c)に示すマッチングは最大3次元マッチングであり、 Tから要素を追加することで拡張することはできません。

2 次元マッチングもまったく同じように定義できます。XとY を有限集合とし、T をX  ×  Yのサブセットとします。ここで、M  ⊆  Tは、次の条件が満たされる場合、2 次元マッチングです。任意の 2 つの異なるペア ( x ₁、  y ₁ ) ∈  Mおよび ( x ₂、  y ₂ ) ∈  Mについて、 x ₁  ≠  x ₂かつy ₁  ≠  y ₂が成り立ちます。

2 次元マッチングの場合、集合T は二部グラフ G  = ( X ,  Y ,  T )の辺の集合として解釈できます。 Tの各辺はXの頂点とYの頂点を接続します。2 次元マッチングはグラフGのマッチング、つまり隣接しない辺のペアの集合です。

したがって、3 次元マッチングは、ハイパーグラフへのマッチングの一般化として解釈できます。つまり、集合X、Y、Zには頂点が含まれ、Tの各要素はハイパーエッジであり、集合Mはペアワイズ非隣接エッジ (共通の頂点を持たないエッジ) で構成されます。2 次元マッチングの場合、 Y = Z となります。

3次元マッチングはセットパッキングの特殊なケースです。Tの各要素 ( x、  y、  z )をX  ∪  Y  ∪  Zのサブセット { x、  y、  z }として解釈できます。この場合、3次元マッチングM はペアワイズで互いに素なサブセットで構成されます。

計算複雑性理論において、3 次元マッチング (3DM) は、集合Tと整数kが与えられたときに、 | M | ≥  kを満たす3 次元マッチングM  ⊆  T が存在するかどうかを判定する、という決定問題の名前です。

この決定問題はNP 完全であることが知られており、カープの 21 の NP 完全問題の 1 つです。^[1] k  = | X | = | Y | = | Z |という特殊なケースでも、また各要素が最大 3 つの集合に含まれる場合、つまり 3 正則ハイパーグラフで完全マッチングが必要な場合でも、NP 完全です。^{[1] [2] [3]}この場合、 3 次元マッチングは集合の詰め込みであるだけでなく、正確な被覆でもあります。集合MはX、Y、Zの各要素を正確に 1 回被覆します。^[4]証明は3SATからの還元により行われます。3SAT インスタンスが与えられた場合、次のように 3DM インスタンスを構築します。^{[2] [5]}

• 各変数x _iには、車輪のような形の「変数ガジェット」があります。これは、重なり合った 3 つ組で構成されています。3 つ組の数は、式内のx _iの出現回数の 2 倍です。ガジェット内のすべての頂点をカバーする方法は 2 つあります。1 つは、偶数インデックスの 3 つ組をすべて選択する方法で、もう 1 つは、奇数インデックスの 3 つ組をすべて選択する方法です。これらの 2 つの方法は、x _{i を}「true」または「false」に設定することに対応しています。「true」を選択すると、奇数インデックスの 3 つ組ごとに 1 つの頂点がカバーされず、「false」を選択すると、偶数インデックスの 3 つ組ごとに 1 つの頂点がカバーされません。
• 各節x _i u x _j u x _kには、バラのような形の「節ガジェット」があります。節ガジェットは、節内の各変数に 1 つずつ対応する 3 つの重なり合ったトリプレットで構成されています。変数ガジェットの選択によってノードの少なくとも 1 つがカバーされていない場合、節ガジェットはカバーされます。
• 2 つ以上のノードがカバーされないままになる可能性があるため、「ガベージ コレクション ガジェット」も必要です。これは、より大きなバラのような形をしています。これは、変数ガジェットでカバーされないままになる可能性のある各頂点ごとに 1 つずつ、複数の重なり合った 3 つ組で構成されています。このようなガジェットの数は、満足のいく割り当てがある場合にのみ、正確にカバーできるように決定されます。

密なハイパーグラフにおける3DMを解く多項式時間アルゴリズムが存在する。^{[6] [7]}

最大3 次元マッチングは、最大の 3 次元マッチングです。計算複雑性理論では、これは次の最適化問題の名前でもあります: 集合Tが与えられたときに、 |M| を最大化する3 次元マッチングM  ⊆  Tを見つけます。

上で説明した決定問題は NP 完全であるため、この最適化問題はNP 困難であり、したがって最大 3 次元マッチングを見つけるための多項式時間アルゴリズムは存在しないと思われます。ただし、最大二部マッチング(最大 2 次元マッチング) を見つけるための効率的な多項式時間アルゴリズムは存在します。たとえば、ホップクロフト-カープ アルゴリズムです。

3次元マッチングには非常に単純な多項式時間の3近似アルゴリズムがあります。任意の最大3次元マッチングを見つけます。^[8]最大マッチングが最大マッチングの2倍以内であるのと同様に、^[9]最大3次元マッチングは最大3次元マッチングの3倍以内です。

任意の定数ε>0に対して、3次元マッチングのための多項式時間(4/3 + ε)近似アルゴリズムが存在する。^[10]

しかし、より良い近似係数を得ることはおそらく難しい。この問題はAPX完全であり、つまり、ある定数内で近似することは難しい。 ^{[11] [12] [8]}

最大3次元マッチングの近似係数95/94、最大4次元マッチングの近似係数48/47を達成するのはNP困難である。各要素が正確に2回出現するインスタンスに制限した場合でも、困難さは変わらない。^[13]

超並列通信モデルにおける3次元マッチングには様々なアルゴリズムがある。^[14]

• NP完全問題のリスト
• レインボー独立集合– 3 次元マッチングから簡約できる問題。
• 数値3次元マッチング

• Ausiello, Giorgio; Crescenzi, Pierluigi; Gambosi, Giorgio; Kann, Viggo; Marchetti-Spaccamela, Alberto; Protasi, Marco (2003)、『複雑性と近似：組み合わせ最適化問題とその近似可能性特性』、Springer。
• クレッシェンツィ、ピエルルイジ。カン、ヴィゴ。ハルドルソン、マグナス。Karpinski, マレク; Woeginger、Gerhard (2000)、「最大 3 次元マッチング」、NP 最適化問題の概要。
• カン、ヴィゴ（1991）、「最大境界付き3次元マッチングはMAX SNP完全である」、情報処理レター、37（1）：27–35、doi：10.1016/0020-0190（91）90246-E。
• Karp, Richard M. (1972)、「組合せ問題における縮約可能性」、Miller, Raymond E.、Thatcher, James W. (編)、Computations of Computer Computations、Plenum、pp. 85–103。
• Karpinski, Marek ; Rucinski, Andrzej; Szymanska, Edyta (2009)、「密なハイパーグラフ上の完全マッチング問題の複雑性」、ISAAC '09 Proceedings of the 20th International Symposium on Algorithms、Lecture Notes in Computer Science、5878 : 626–636、doi :10.1007/978-3-642-10631-6_64、ISBN 978-3-642-10630-9。
• Keevash, Peter; Knox, Fiachra; Mycroft, Richard (2013)、「密なハイパーグラフにおける多項式時間完全マッチング」、第 45 回 ACM コンピューティング理論シンポジウムの議事録、pp. 311–320、arXiv : 1307.2608、Bibcode :2013arXiv1307.2608K、doi :10.1145/2488608.2488647、ISBN 9781450320290、S2CID  5393523。
• パパディミトリウ、クリストス H. ;シュタイグリッツ、ケネス(1998)、組み合わせ最適化: アルゴリズムと複雑性、ドーバー出版。

• JavaScript で実装されたインタラクティブな視覚化