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[réf. 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 est [réf. nécessaire].
- 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
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
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
- Liste de problèmes NP-complets
- Couverture par sous-graphes bipartis complets
- Intersection number (graph theory) (en)
Notes et références
- (en) Cet article est partiellement ou en totalité issu de l’article de Wikipédia en anglais intitulé « Bipartite dimension » (voir la liste des auteurs).
- ↑ « MR: Matches for: MR=657202 », sur mathscinet.ams.org (consulté le )
- ↑ (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 )
- ↑ (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 )
- ↑ (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 )
- ↑ (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 )
- ↑ (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 )
- ↑ R. G. Downey, Parameterized complexity, Springer, (ISBN 0-387-94883-X et 978-0-387-94883-6, OCLC 37004493, lire en ligne)
- ↑ (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 )
- ↑ 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
- ↑ 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
Portail des mathématiques