Appariement à 3 dimensions

La figure à droite illustre un appariement à 3 dimensions. L'ensemble ${\displaystyle X}$ est représenté par des points rouges, ${\displaystyle Y}$ par des points bleus et ${\displaystyle Z}$ par des points verts. La figure (a) montre l'ensemble ${\displaystyle T}$ donné ; chaque triplet est dessiné dans une zone grisée. La figure (b) montre un appariement à 3 dimensions composé de deux éléments, et la figure (c) montre un appariement composé de trois éléments.

L'appariement de la figure (c) est de taille maximum : il n'en existe pas de taille plus grande, alors que l'appariement de la figure (b), tout en n'étant pas de taille maximum, est maximal : il ne peut pas être agrandi en un appariement plus grand.

Un couplage, ou appariement à 2 dimensions, peut être défini de manière tout à fait analogue : soient ${\displaystyle X}$ et ${\displaystyle Y}$ deux ensembles finis disjoints, et soit ${\displaystyle T}$ une partie de ${\displaystyle X\times Y}$. Une partie ${\displaystyle M\subseteq T}$ est un couplage si, pour toute paire de couples distincts ${\displaystyle (x_{1},y_{1})}$ et ${\displaystyle (x_{2},y_{2})}$ de ${\displaystyle M}$, on a ${\displaystyle x_{1}\neq x_{2}}$ et ${\displaystyle y_{1}\neq y_{2}}$.

Dans le cas de l’appariement en dimension 2, l'ensemble ${\displaystyle T}$ peut être interprété comme l'ensemble des arêtes d'un graphe biparti ${\displaystyle G=(X\cup Y,T)}$, chaque arête de ${\displaystyle T}$ reliant un sommet de ${\displaystyle X}$ à un sommet de ${\displaystyle Y}$. Un appariement à 2 dimensions est alors couplage dans le graphe ${\displaystyle G}$, c'est-à-dire un ensemble d'arêtes deux-à-deux non adjacentes.

De même, un appariement à 3 dimensions peut être interprété comme une généralisation des couplages aux hypergraphes : les ensembles ${\displaystyle X,Y}$ et ${\displaystyle Z}$ contiennent les sommets, chaque triple de ${\displaystyle T}$ est une hyper-arête, et l'ensemble ${\displaystyle M}$ est formé d'hyper-arêtes deux-à-deux disjointes, c'est-à-dire sans sommet commun.

Un appariement à 3 dimensions est un cas particulier du set packing: on peut interpréter chaque triplet ${\displaystyle (x,y,z)}$ de ${\displaystyle T}$ comme un sous-ensemble ${\displaystyle \{x,y,z\}}$ de ${\displaystyle X\cup Y\cup Z}$ ; un appariement à 3 dimensions ${\displaystyle M}$ consiste alors en des sous-ensembles deux-à-deux disjoints.

Le problème est APX-complet ; en d'autres termes, il est difficile de l'approximer avec un facteur constant[7] - [8] - [9]. En revanche, pour toute constante ${\displaystyle \varepsilon >0}$, il existe un algorithme d'approximation en temps polynomial de facteur ${\displaystyle 3/2+\varepsilon }$[7] - [8].

Il existe un algorithme polynomial très simple pour calculer une appariement à 3 dimensions avec un facteur d'approximation 3 : il suffit de trouver un appariement à 3 dimensions quelconque qui ne peut être augmenté (un appariement maximal)[9]. Il n'est pas forcément maximum, mais tout comme une couplage maximal est un couplage maximum à un facteur 1/2 près, un appariement à 3 dimensions maximal est maximum à un facteur 1/3 près.

• Théorie des graphes
• Couplage (théorie des graphes)
• Liste de problèmes NP-complets

• Giorgio Ausiello, Pierluigi Crescenzi, Giorgio Gambosi, Viggo Kann, Alberto Marchetti-Spaccamela et Marco Protasi, Complexity and Approximation : Combinatorial Optimization Problems and Their Approximability Properties, Springer, 2003.
• Pierluigi Crescenzi, Viggo Kann, Magnús Halldórsson, Marek Karpinski et Gerhard Woeginger, « Maximum 3-dimensional matching », dans A Compendium of NP Optimization Problems, 2000 (lire en ligne).
• (en) Michael Garey et David S. Johnson, Computers and Intractability : A Guide to the Theory of NP-Completeness, W.H. Freeman, 1979 (ISBN 0-7167-1045-5).
• Viggo Kann, « Maximum bounded 3-dimensional matching is MAX SNP-complete », Information Processing Letters, vol. 37, n^o 1,‎ 1991, p. 27–35 (DOI 10.1016/0020-0190(91)90246-E).
• (en) Richard M. Karp, « Reducibility Among Combinatorial Problems », dans Raymond E. Miller et James W. Thatcher, Complexity of Computer Computations, Plenum, 1972 (ISBN 978-1-4684-2003-6, DOI 10.1007/978-1-4684-2001-2_9, lire en ligne), p. 85-103
• Marek Karpinski, Andrzej Rucinski et Edyta Szymanska, « The Complexity of Perfect Matching Problems on Dense Hypergraphs », ISAAC '09 Proceedings of the 20th International Symposium on Algorithms,‎ 2009, p. 626-636 (DOI 10.1007/978-3-642-10631-6_64).
• Peter Keevash, Fiachra Knox et Richard Mycroft, « Polynomial-Time perfect matchings in dense hypergraphs », STOC '13 Proceedings of the forty-fifth annual ACM symposium,‎ 2013, p. 311-320 (DOI 10.1145/2488608.2488647).
• Bernhard Korte et Jens Vygen, Combinatorial Optimization : Theory and Algorithms, Springer, 2006, 3^e éd..
• Christos H. Papadimitriou et Kenneth Steiglitz, Combinatorial Optimization : Algorithms and Complexity, Dover Publications, 1998.