Voir la source de Appariement à 3 dimensions

[[Fichier:3-dimensional-matching.svg|vignette|Appariement à 3 dimensions. (a) Donnée ''T''. (b)–(c) Deux solutions. (c) est de taille maximum.]]
En [[mathématiques]], et notamment en [[théorie des graphes]], un '''appariement à 3 dimensions''' (en anglais : ''{{langue|en|3-dimensional matching}}'') est une généralisation du [[couplage (théorie des graphes)|couplage]] (aussi appelé ''appariement en dimension 2'' ) à une situation ternaire qui, techniquement, est celle des [[Hypergraphe|hypergraphes]] dits 3-uniformes. Trouver un appariement à {{nobr|3 dimensions}} de taille maximum est un problème [[NP-difficile]] bien connu en [[théorie de la complexité (informatique théorique)|théorie de la complexité informatique]].

== Définition ==
Soient <math>X, Y</math> et <math>Z</math> trois ensembles finis disjoints, et soit <math>T</math> un sous-ensemble de <math>X\times Y\times Z</math>. Ainsi, <math>T</math> est composé de triplets <math>(x,y,z)</math>, avec <math>x\in X, y\in Y</math> et <math>z\in Z</math>. Une partie <math>M\subseteq T</math> est un '''appariement à 3 dimensions''' si la propriété suivante est vérifiée : pour toute paire de triplets <math>(x_1,y_1,z_1)</math> et <math>(x_2,y_2,z_2)</math> distincts de <math>M</math>, on a <math>x_1\ne x_2</math> ,<math>y_1\ne y_2</math> et <math>z_1\ne z_2</math>. En d'autres termes, si deux triplets diffèrent sur une composante, ils doivent différer sur toutes leurs composantes.

=== Exemple ===
La figure à droite illustre un appariement à 3 dimensions. L'ensemble <math>X</math> est représenté par des points rouges, <math>Y</math> par des points bleus et <math>Z</math> par des points verts. La figure (a) montre l'ensemble <math>T</math> 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.

=== Comparaison avec le couplage ===
Un ''couplage'', ou ''appariement à 2 dimensions'', peut être défini de manière tout à fait analogue : soient <math>X</math> et <math>Y</math> deux ensembles finis disjoints, et soit <math>T</math> une partie de <math>X \times Y</math>. Une partie <math>M\subseteq T</math> est un ''couplage'' si, pour toute paire de couples distincts <math>(x_1,y_1)</math> et <math>(x_2,y_2)</math> de <math>M</math>, on a <math>x_1\ne x_2</math> et <math>y_1\ne y_2</math>. 

Dans le cas de l’appariement en dimension 2, l'ensemble <math>T</math> peut être interprété comme l'ensemble des arêtes d'un [[graphe biparti]] <math>G=(X\cup Y, T)</math>, chaque arête de <math>T</math> reliant un sommet de <math>X</math> à un sommet de <math>Y</math>. Un appariement à 2 dimensions est alors [[couplage (théorie des graphes)|couplage]] dans le graphe <math>G</math>, 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 [[hypergraphe]]s : les ensembles <math>X, Y</math> et <math>Z</math> contiennent les sommets, chaque triple de <math>T</math> est une hyper-arête, et l'ensemble <math>M</math> est formé d'hyper-arêtes deux-à-deux disjointes, c'est-à-dire sans sommet commun.

=== Comparaison avec le ''set packing'' ===
Un appariement à 3 dimensions est un cas particulier du [[set packing]]: on peut interpréter chaque triplet <math>(x,y,z)</math> de <math>T</math> comme un sous-ensemble <math>\{x,y,z\}</math> de <math>X\cup Y\cup Z</math> ; un appariement à 3 dimensions <math>M</math> consiste alors en des sous-ensembles deux-à-deux disjoints.

== Problème de décision ==
En [[théorie de la complexité (informatique théorique)|théorie de la complexité informatique]], le ''problème de l{{'}}appariement à 3 dimensions'' est le nom du [[problème de décision]] suivant : étant donné un ensemble  <math>T</math> et un entier ''k''; décider s'il existe un appariement à 3 dimensions <math>M \subseteq T</math> avec au moins ''k'' éléments.

Ce problème de décision est connu pour être [[Problème NP-complet|NP-complet]] : c'est l'un des fameux [[21 problèmes NP-complets de Karp]]<ref name="karp72">{{harvsp|id =Karp 1972|texte = Karp 1972}}.</ref>. Il existe toutefois des algorithmes polynomiaux pour ce problème dans des cas particuliers, comme celui des hypergraphes « denses »<ref name="Karpinski2009">{{harvsp|Karpinski|Rucinski|Szymanska|2009}}</ref>{{,}}<ref>{{harvsp|Keevash|Knox|Mycroft|2013}}</ref>.

Le problème est NP-complet même dans le cas particulier où <math>k=|X|=|Y|=|Z|</math><ref name="karp72"/>{{,}}<ref name="garey79">{{harvsp|id= Garey Johnson NP|Garey et Johnson 1979}}, Section&nbsp;3.1 et Problème&nbsp;SP1 dans Appendix&nbsp;A.3.1.</ref>{{,}}<ref name="korte06">{{harvsp|Korte|Vygen|2006}}, Section 15.5.</ref>. Dans ce cas, un appariement à 3 dimensions n'est pas seulement un ''set packing'' mais aussi un [[problème de la couverture exacte]] : l'ensemble <math>M</math> couvre chaque élément de <math>X, Y</math> et <math>Z</math> une fois exactement<ref name="papadimitriou98">{{harvsp|Papadimitriou|Steiglitz|1998}}, Section 15.7.</ref>.

== Problème d'optimisation ==
Un ''appariement à 3 dimensions maximum'' est un appariement à 3 dimensions de taille maximum. En théorie de la complexité, c'est aussi le nom du problème d'[[optimisation combinatoire]] suivant : étant donné <math>T</math>, trouver un appariement à 3 dimensions <math>M</math>  de taille maximum. 

Comme le problème de décision est [[Problème NP-complet|NP-complet]], le problème d'optimisation est [[NP-difficile]], et il n'existe donc vraisemblablement pas d'algorithme polynomial pour trouver un appariement à 3 dimensions maximum, alors qu'il existe des algorithmes efficaces en temps polynomial pour la dimension 2, comme l'[[algorithme de Hopcroft-Karp|algorithme de Hopcroft et Karp]].

=== Algorithmes d'approximation ===
Le problème est [[APX (complexité)|APX-complet]] ; en d'autres termes, il est difficile de l'[[Algorithme d'approximation|approximer]] avec un facteur constant<ref name="compendium">{{harvsp|Crescenzi|Kann|Halldórsson|Karpinski|2000}}.</ref>{{,}}<ref name="ausiello03">{{harvsp|Ausiello|Crescenzi|Gambosi|Kann|2003}}, {{nobr|Problème SP1}} de l'{{nobr|Appendice B}}.</ref>{{,}}<ref name="kann91">{{harvsp|Kann|1991}}.</ref>. En revanche, pour toute constante <math>\varepsilon>0</math>, il existe un algorithme d'approximation en temps polynomial de facteur <math>3/2+\varepsilon</math><ref name="compendium"/>{{,}}<ref name="ausiello03"/>.

Il existe un algorithme polynomial très simple pour calculer une appariement à {{nobr|3 dimensions}} avec un facteur d'approximation 3 : il suffit de trouver un appariement à {{nobr|3 dimensions}} quelconque qui ne peut être augmenté (un appariement maximal)<ref name="kann91"/>. 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.

== Notes et références ==
{{Références}}
{{Traduction/Référence|en|3-dimensional matching|716627279|type=note}}

== Voir aussi ==
=== Articles connexes ===
* [[Théorie des graphes]]
* [[Couplage (théorie des graphes)]]
*[[Liste de problèmes NP-complets]]

=== Bibliographie ===
*{{Ouvrage
 | prénom1=Giorgio
 | nom1=Ausiello
 | prénom2=Pierluigi
 | nom2=Crescenzi
 | prénom3=Giorgio
 | nom3=Gambosi
 | prénom4=Viggo
 | nom4=Kann
 | prénom5=Alberto
 | nom5=Marchetti-Spaccamela
 | prénom6=Marco
 | nom6=Protasi
 | titre=Complexity and Approximation : Combinatorial Optimization Problems and Their Approximability Properties
 | éditeur=[[Springer Science+Business Media|Springer]]
 | année=2003
 | isbn=
}}.
*{{chapitre
 | nom1=Crescenzi | prénom1=Pierluigi
 | nom2=Kann | prénom2=Viggo
 | nom3=Halldórsson | prénom3=Magnús
 | nom4=Karpinski | prénom4=Marek | lien auteur4=Marek Karpinski
 | nom5=Woeginger | prénom5=Gerhard | lien auteur5 =Gerhard Woeginger
 | titre ouvrage=A Compendium of NP Optimization Problems
 | titre=Maximum 3-dimensional matching
 | url=http://www.nada.kth.se/~viggo/wwwcompendium/node143.html
 | année=2000
}}.
*{{Garey Johnson NP}}.
*{{article
 | nom=Kann | prénom=Viggo
 | titre=Maximum bounded 3-dimensional matching is MAX SNP-complete
 | journal=Information Processing Letters
 | volume=37
 | numéro=1
 | année=1991
 | pages=27–35
 | doi=10.1016/0020-0190(91)90246-E
}}.
*{{Reducibility Karp 1972}}
*{{article
 | nom1=Karpinski | prénom1=Marek | lien auteur1=Marek Karpinski
 | nom2=Rucinski  | prénom2=Andrzej
 | nom3=Szymanska | prénom3=Edyta
 | titre=The Complexity of Perfect Matching Problems on Dense Hypergraphs
 | journal=ISAAC '09 Proceedings of the 20th International Symposium on Algorithms
 | pages = 626-636
 | année=2009
 | doi=10.1007/978-3-642-10631-6_64
}}.
*{{article
 | nom1=Keevash | prénom1=Peter
 | nom2=Knox | prénom2= Fiachra
 | nom3=Mycroft | prénom3=Richard
 | titre=Polynomial-Time perfect matchings in dense hypergraphs
 | journal=STOC '13 Proceedings of the forty-fifth annual ACM symposium
 | pages=311-320
 | année=2013
 | doi=10.1145/2488608.2488647
}}.
*{{Ouvrage
 | prénom1=Bernhard
 | nom1=Korte
 | lien auteur1=Bernhard Korte
 | prénom2=Jens
 | nom2=Vygen
 | titre=Combinatorial Optimization
 | sous-titre=Theory and Algorithms
 | éditeur=[[Springer Science+Business Media|Springer]]
 | année=2006
 | numéro d'édition=3
 | isbn=
}}.
*{{Ouvrage
 | prénom1=Christos H.
 | nom1=Papadimitriou
 | lien auteur1=Christos Papadimitriou
 | prénom2=Kenneth
 | nom2=Steiglitz
 | lien auteur2=Kenneth Steiglitz
 | titre=Combinatorial Optimization
 | sous-titre=Algorithms and Complexity
 | éditeur=[[Dover Publications]]
 | année=1998
 | isbn=
}}.

{{Palette 21 problèmes NP-complets de Karp}}

{{Portail|informatique théorique|mathématiques}}

[[Catégorie:Couplage (théorie des graphes)]]
[[Catégorie:Problème NP-complet]]
[[Catégorie:Combinatoire]]