Dans le domaine mathématique de la théorie des graphes et de l'optimisation combinatoire, la dimension bipartie d'un graphe G = (V, E) non orienté est le nombre minimum de sous-graphes bipartis complets nécessaires pour couvrir toutes les arêtes de E. Un ensemble de sous-graphes bipartis complets couvrant toutes les arêtes de G est appelé une couverture par sous-graphes bipartis complets, ou couverture biclique. La dimension bipartie d'un graphe G est souvent notée d(G).
Exemple Considérons un graphe G = (V, E) qui s'avère être biparti. Voici un exemple de couverture sous-graphes bipartis complets de G :
Formules pour quelques classes de graphes
La dimension bipartie d'un graphe complet est .
La dimension bipartie d'un graphe couronne à 2n sommets est , où:
La dimension bipartie d'un graphe grille de taille est si est pair et pour deux entiers et est sinon.
La dimension bipartie de nombreux graphes particuliers a déjà été déterminée : par exemple, pour le chemin , et pour le cycle , .
Algorithmique Le calcul de la dimension bipartie d'un graphe G donné est un problème d'optimisation. Le problème de décision associé à la dimension bipartie peut être formulé ainsi : Entrée : Un graphe non orienté et un entier positif . Sortie : Oui, s'il existe une couverture de G par sous-graphes bipartis complets de cardinal inférieur à ; non sinon.
Ce problème est appelé problème GT18 dans le livre de Garey et Johnson sur les problèmes NP-complets, et est une reformulation d'un autre problème sur les familles d'ensembles finis, le problème Set Basis nommé SP7.
Il a été prouvé que le problème GT18 est NP-complet, et ce même pour les graphes bipartis. Il reste NP-dur si l'on se restreint aux graphes dont la dimension bipartie est au pire en , avec n la taille de l'instance.
De plus, si P ≠ NP, ce problème ne peut être approximé finement : même pour les graphes bipartis, pour fixé, on ne peut pas approximer à plus de . Cependant, on peut montrer grâce à de la kernelisation que ce problème est FPT. Ainsi, pour un graphe biparti à n sommets donné, on peut décider en , avec si sa dimension bipartie est inférieure ou égal à .
Applications Le calcul de la dimension bipartie d'un graphe peut être utile dans différents contextes. Dans des systèmes informatiques, différents utilisateurs peuvent avoir accès à différentes ressources. Dans un système à Contrôle d'accès à base de rôles, un rôle donne les droits accès à certaines ressources. Un utilisateur peut avoir plusieurs rôles, et doit avoir accès à toutes les ressources liées à chacun de ses rôles. De plus, plusieurs utilisateurs peuvent avoir le même rôle. Le role mining problem consiste à trouver le nombre minimum de rôles, tels que chaque utilisateur a accès à des ressources spécifiques. L'ensemble des utilisateurs, combiné avec l'ensemble des ressources, forme un graphe biparti dont les arêtes sont les permissions. Tout sous-graphes bipartis complets est un rôle potentiel, et la solution du role mining problem est justement une couverture par sous-graphes bipartis complets minimaleEne, Alina; Horne, William G.; Milosavljevic, Nikola; Rao, Prasad; Schreiber, Robert; Tarjan, Robert Endre (2008), "Fast exact and heuristic methods for role minimization problems", in Ray, Indrakshi; Li, Ninghui (eds.), 13th ACM Symposium on Access Control Models and Technologies (SACMAT 2008), ACM, pp. 1–10.
Un scénario similaire se rencontre en sécurité des systèmes d'information, plus précisément en sécurité de télédiffusion. Dans ce cas-là, plusieurs messages doivent être envoyés à certains ensembles de destinataires, via un moyen de communication non sécurisé. Chaque message doit être codé à partir d'une clé connue uniquement des destinataires. Chacun d'entre eux peut avoir plusieurs clés, et chaque clés peut être possédée par plusieurs destinataires. L'optimum key generation problem consiste à trouver un nombre minimal de clé pour que chaque transmissions soit sécurisé. Ce problème peut être modélisé par un graphe biparti, dont la couverture par sous-graphes bipartis complets minimale correspond à une solution du problèmeShu, Guoqiang; Lee, David; Yannakakis, Mihalis (2006), "A note on broadcast encryption key management with applications to large scale emergency alert systems.", 20th International Parallel and Distributed Processing Symposium (IPDPS 2006), IEEE.
Voir aussi Liste de problèmes NP-complets Couverture par sous-graphes bipartis complets Nombre d'intersection
Notes et références
Catégorie:Problème NP-complet Catégorie:Invariant de graphe Bipartie