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 souventModèle:Référence nécessaire 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 :

• Exemple de couverture par sous-graphes bipartis complets
• 
  Un graphe G biparti
• 
  ... et une couverture par quatre sous-graphes bipartis complets
• 
  1. Le sous-graphe biparti complet rouge
• 
  2. Le sous-graphe biparti complet bleu
• 
  3. Le sous-graphe biparti complet vert
• 
  4. Le sous-graphe biparti complet noir

Formules pour quelques classes de graphes

• La dimension bipartie d'un graphe complet $K_n$ est $\lceil {\log }_{2}n\rceil$Modèle:Référence nécessaire.

• La dimension bipartie d'un graphe couronne à 2n sommets est $\sigma (n)$, où: $\sigma (n)=\min \{k\mid n\le (\genfrac{}{}{0ex}{}{k}{\lfloor k/2\rfloor })\}$

• La dimension bipartie d'un graphe grille de taille $n\times m$ est $\frac{nm}{2}-1$ si $m$ est pair et $n-1=k(m-1)+2\ell$ pour deux entiers $0\le l<k$ et est$\lfloor \frac{nm}{2}\rfloor$ sinon.

• La dimension bipartie de nombreux graphes particuliers a déjà été déterminée : par exemple, pour le chemin $P_n$, $d(P_n)=\lfloor n/2\rfloor$ et pour le cycle $C_n$, $d(C_n)=\lceil n/2\rceil$.

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 $G=(V,E)$ non orienté et un entier positif $k$.

Sortie : Oui, s'il existe une couverture de G par sous-graphes bipartis complets de cardinal inférieur à $k$ ; 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 $O(\log n)$, 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 $ϵ>0$ fixé, on ne peut pas approximer à plus de $|V{|}^{1/3-ϵ}$. 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 $O(f(k))+n^3$, avec $f(k)=2^{k{2}^{k-1}+3k}$ si sa dimension bipartie est inférieure ou égal à $k$.

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
• Modèle:Lien