problème de couplage triparti

**lyxthe** · 25/09/2007, 17h12

Salut. Problème posé en cours de master II :
Prouver que le problème est NP-Complet :
Problème de couplage triparti :
Données : un ensemble de T triplets dans BxGxH, avec B, G, H possédant n éléments.
Question : existe-t-il un sous ensemble S inclus dans T de n triplets deux à deux disjoints : |S|=n et S un ensemble de triplets distincts.

Voilà le résultat de nos avancées.
Le problème est forcément NP puisqu'un certificat est vérifiable en temps polynomial. Il suffit de compter si l'ensemble S donné en réponse possède bien n triplets et qu'aucuns des éléments d'un triplet ne se retrouve dans un autre.
On doit donc trouver une réduction d'un problème NP-complet vers celui-ci. A priori nous pension que 3-Sat était un bon candidat mais impossible d'avancer. Sinon nous avons penser à Stable.

Si quelqu'un a des idées à nous partager.... Pour stable on a des idées. S'il est possible de trouver un algorithme transformant un graphe quelconque en une instance de notre problème on a gagné, on sait résoudre.
Pour de plus amples infos merci de demander.

alex_pi · 25/09/2007, 19h12

Envoyé par lyxthe

Question : existe-t-il un sous ensemble S inclus dans T de n triplets deux à deux disjoints : |S|=n et S un ensemble de triplets distincts.

deux triplets (a,b,c) et (a',b',c') sont distincts si et seulement si a != a' ET b != b' ET c != c' c'est bien ça ? Parce que si ce sont des ou, c'est trivial... (enfin, trivialement pas NP-complet quoi :-))