Dimension bipartie — Wikipédia

Dans le domaine mathématique de la théorie des graphes et de l'optimisation combinatoire, la dimension bipartie d'un graphe G = (VE) 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[réf. nécessaire] notée d(G).

Exemple[modifier | modifier le code]

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[modifier | modifier le code]

  • La dimension bipartie d'un graphe couronne à 2n sommets est , où: [1]
  • La dimension bipartie d'un graphe grille de taille est si est pair et pour deux entiers et est sinon[2].
  • La dimension bipartie de nombreux graphes particuliers a déjà été déterminée : par exemple, pour le chemin , et pour le cycle , [3].

Algorithmique[modifier | modifier le code]

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[4], 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[5].

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 [6]. Cependant, on peut montrer grâce à de la kernelisation que ce problème est FPT[7]. Ainsi, pour un graphe biparti à n sommets donné, on peut décider en , avec si sa dimension bipartie est inférieure ou égal à [8].

Applications[modifier | modifier le code]

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[9].

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[10].

Voir aussi[modifier | modifier le code]

Notes et références[modifier | modifier le code]

  1. « MR: Matches for: MR=657202 », sur mathscinet.ams.org (consulté le )
  2. (en) Krystal Guo, Tony Huynh et Marco Macchia, « The Biclique Covering Number of Grids », The Electronic Journal of Combinatorics,‎ , P4.27–P4.27 (ISSN 1077-8926, DOI 10.37236/8316, lire en ligne, consulté le )
  3. (en) « Bipartite dimensions and bipartite degrees of graphs », Discrete Mathematics, vol. 160, nos 1-3,‎ , p. 127–148 (ISSN 0012-365X, DOI 10.1016/0012-365X(95)00154-O, lire en ligne, consulté le )
  4. (en) « Contentment in graph theory: Covering graphs with cliques », Indagationes Mathematicae (Proceedings), vol. 80, no 5,‎ , p. 406–424 (ISSN 1385-7258, DOI 10.1016/1385-7258(77)90055-5, lire en ligne, consulté le )
  5. (en) Lee-Ad J. Gottlieb, John E. Savage et Arkady Yerukhimovich, « Efficient Data Storage in Large Nanoarrays », Theory of Computing Systems, vol. 38, no 4,‎ , p. 503–536 (ISSN 1433-0490, DOI 10.1007/s00224-004-1196-9, lire en ligne, consulté le )
  6. (en) Hermann Gruber et Markus Holzer, « Inapproximability of Nondeterministic State and Transition Complexity Assuming P ≠ NP », Developments in Language Theory, Springer, lecture Notes in Computer Science,‎ , p. 205–216 (ISBN 978-3-540-73208-2, DOI 10.1007/978-3-540-73208-2_21, lire en ligne, consulté le )
  7. R. G. Downey, Parameterized complexity, Springer, (ISBN 0-387-94883-X et 978-0-387-94883-6, OCLC 37004493, lire en ligne)
  8. (en) Igor Nor, Danny Hermelin, Sylvain Charlat et Jan Engelstadter, « Mod/Resc Parsimony Inference », Combinatorial Pattern Matching, Springer, lecture Notes in Computer Science,‎ , p. 202–213 (ISBN 978-3-642-13509-5, DOI 10.1007/978-3-642-13509-5_19, lire en ligne, consulté le )
  9. Ene, 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
  10. Shu, 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