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.