Appariement à 3 dimensions

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 : 3-dimensional matching) est une généralisation du couplage (aussi appelé appariement en dimension 2 ) à une situation ternaire qui, techniquement, est celle des hypergraphes dits 3-uniformes. Trouver un appariement à 3 dimensions de taille maximum est un problème NP-difficile bien connu en théorie de la complexité informatique.

Définition

Soient ${\displaystyle X,Y}$ et ${\displaystyle Z}$ trois ensembles finis disjoints, et soit ${\displaystyle T}$ un sous-ensemble de ${\displaystyle X\times Y\times Z}$. Ainsi, ${\displaystyle T}$ est composé de triplets ${\displaystyle (x,y,z)}$, avec ${\displaystyle x\in X,y\in Y}$ et ${\displaystyle z\in Z}$. Une partie ${\displaystyle M\subseteq T}$ est un appariement à 3 dimensions si la propriété suivante est vérifiée : pour toute paire de triplets ${\displaystyle (x_{1},y_{1},z_{1})}$ et ${\displaystyle (x_{2},y_{2},z_{2})}$ distincts de ${\displaystyle M}$, on a ${\displaystyle x_{1}\neq x_{2}}$ ,${\displaystyle y_{1}\neq y_{2}}$ et ${\displaystyle z_{1}\neq z_{2}}$. 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 ${\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.

Comparaison avec le couplage

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.

Comparaison avec le set packing

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.

Problème de décision

En 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 ${\displaystyle T}$ et un entier k; décider s'il existe un appariement à 3 dimensions ${\displaystyle M\subseteq T}$ avec au moins k éléments.

Ce problème de décision est connu pour être NP-complet : c'est l'un des fameux 21 problèmes NP-complets de Karp^[1]. Il existe toutefois des algorithmes polynomiaux pour ce problème dans des cas particuliers, comme celui des hypergraphes « denses »^[2],[3].

Le problème est NP-complet même dans le cas particulier où ${\displaystyle k=|X|=|Y|=|Z|}$^[1],[4],[5]. 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 ${\displaystyle M}$ couvre chaque élément de ${\displaystyle X,Y}$ et ${\displaystyle Z}$ une fois exactement^[6].

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é ${\displaystyle T}$, trouver un appariement à 3 dimensions ${\displaystyle M}$ de taille maximum.

Comme le problème de décision est 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 et Karp.

Algorithmes d'approximation

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.

Notes et références

1. Karp 1972.
2. Karpinski, Rucinski et Szymanska 2009
3. Keevash, Knox et Mycroft 2013
4. Garey et Johnson 1979, Section 3.1 et Problème SP1 dans Appendix A.3.1.
5. Korte et Vygen 2006, Section 15.5.
6. Papadimitriou et Steiglitz 1998, Section 15.7.
7. Crescenzi et al. 2000.
8. Ausiello et al. 2003, Problème SP1 de l'Appendice B.
9. Kann 1991.

(en) Cet article est partiellement ou en totalité issu de l’article de Wikipédia en anglais intitulé « 3-dimensional matching » (voir la liste des auteurs).

Voir aussi

Articles connexes

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

Bibliographie

• 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.