Dimension bipartie

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

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ème.

Voir aussi 
 Liste de problèmes NP-complets
 Couverture par sous-graphes bipartis complets

Notes et références 

Problème NP-complet
Invariant de graphe
Bipartie