# 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 :
* 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$.
* La dimension bipartie d'un graphe couronne à 2n sommets est $\sigma (n)$, où: $\sigma (n)=\min \left\{\,k\mid n\leq {\binom {k}{\lfloor k/2\rfloor }}\,\right\}$
* 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\leq l<k$ et est${\big \lfloor }{\frac {nm}{2}}{\big \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 $\epsilon >0$ fixé, on ne peut pas approximer à plus de $|V|^{1/3-\epsilon }$. 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^{k2^{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.