Appariement à 3 dimensions

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 $X,Y$ et $Z$ trois ensembles finis disjoints, et soit $T$ un sous-ensemble de $X\times Y\times Z$ . Ainsi, $T$ est composé de triplets $(x,y,z)$ , avec $x\in X,y\in Y$ et $z\in Z$ . Une partie $M\subseteq T$ est un appariement à 3 dimensions si la propriété suivante est vérifiée : pour toute paire de triplets $(x_{1},y_{1},z_{1})$ et $(x_{2},y_{2},z_{2})$ distincts de $M$ , on a $x_{1}\neq x_{2}$ , $y_{1}\neq y_{2}$ et $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 $X$ est représenté par des points rouges, $Y$ par des points bleus et $Z$ par des points verts. La figure (a) montre l'ensemble $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 $X$ et $Y$ deux ensembles finis disjoints, et soit $T$ une partie de $X\times Y$ . Une partie $M\subseteq T$ est un couplage si, pour toute paire de couples distincts $(x_{1},y_{1})$ et $(x_{2},y_{2})$ de $M$ , on a $x_{1}\neq x_{2}$ et $y_{1}\neq y_{2}$ .

Dans le cas de l’appariement en dimension 2, l'ensemble $T$ peut être interprété comme l'ensemble des arêtes d'un graphe biparti $G=(X\cup Y,T)$ , chaque arête de $T$ reliant un sommet de $X$ à un sommet de $Y$ . Un appariement à 2 dimensions est alors couplage dans le graphe $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 $X,Y$ et $Z$ contiennent les sommets, chaque triple de $T$ est une hyper-arête, et l'ensemble $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 $(x,y,z)$ de $T$ comme un sous-ensemble $\{x,y,z\}$ de $X\cup Y\cup Z$ ; un appariement à 3 dimensions $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 $T$ et un entier k; décider s'il existe un appariement à 3 dimensions $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ù $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 $M$ couvre chaque élément de $X,Y$ et $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é $T$ , trouver un appariement à 3 dimensions $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 $\varepsilon >0$ , il existe un algorithme d'approximation en temps polynomial de facteur $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

↑ ^{a et b} Karp 1972.
↑ Karpinski, Rucinski et Szymanska 2009
↑ Keevash, Knox et Mycroft 2013
↑ Garey et Johnson 1979, Section 3.1 et Problème SP1 dans Appendix A.3.1.
↑ Korte et Vygen 2006, Section 15.5.
↑ Papadimitriou et Steiglitz 1998, Section 15.7.
↑ ^{a et b} Crescenzi et al. 2000.
↑ ^{a et b} Ausiello et al. 2003, Problème SP1 de l'Appendice B.
↑ ^{a et b} 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

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.

[karp72-1] {a et b} Karp 1972.

[Karpinski2009-2] Karpinski, Rucinski et Szymanska 2009

[3] Keevash, Knox et Mycroft 2013

[garey79-4] Garey et Johnson 1979, Section 3.1 et Problème SP1 dans Appendix A.3.1.

[korte06-5] Korte et Vygen 2006, Section 15.5.

[papadimitriou98-6] Papadimitriou et Steiglitz 1998, Section 15.7.

[compendium-7] {a et b} Crescenzi et al. 2000.

[ausiello03-8] {a et b} Ausiello et al. 2003, Problème SP1 de l'Appendice B.

[kann91-9] {a et b} Kann 1991.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]