En los campos matemáticos de la teoría de grafos y optimización combinatoria , la dimensión bipartito o número cubierta biclique de un gráfico G = ( V , E ) es el número mínimo de bicliques (es decir subgraphs bipartitos completos), necesaria para cubrir todos los bordes en E . Una colección de bicliques que cubre todos los bordes en G se denomina cubierta de borde biclicua o, a veces, cubierta biclique . La dimensión bipartita de G a menudo se denota con el símbolo d ( G).
Ejemplo
En los siguientes diagramas se da un ejemplo de una cubierta de borde biclicua:
Un gráfico bipartito ...
... y una cubierta con cuatro bicliques
el biclique rojo de la portada
el biclique azul de la portada
el biclique verde de la portada
el biclique negro de la portada
Fórmulas de dimensión bipartita para algunos gráficos
La dimensión bipartita del gráfico completo de n - vértices , es .
La dimensión bipartita de un gráfico de corona de vértice 2n es igual a, dónde
es la función inversa del coeficiente binomial central ( de Caen, Gregory & Pullman 1981 ).
La dimensión bipartita del gráfico de celosía es, Si es par y para algunos enteros ; y esde lo contrario ( Guo, Huynh y Macchia 2019 ).
Fishburn y Hammer (1996) determinan la dimensión bipartita para algunos gráficos especiales. Por ejemplo, el camino posee y el ciclo posee .
Calcular la dimensión bipartita
La tarea computacional de determinar la dimensión bipartita para un gráfico G dado es un problema de optimización . El problema de decisión para la dimensión bipartita puede expresarse como:
- INSTANCIA: Un gráfico y un entero positivo .
- PREGUNTA: ¿Admite G una cubierta de borde biclicua que contiene como máximo bicliques?
Este problema aparece como problema GT18 en el libro clásico de Garey y Johnson sobre NP- completitud , y es una reformulación bastante sencilla de otro problema de decisión sobre familias de conjuntos finitos.
El problema de la base establecida aparece como el problema SP7 en el libro de Garey y Johnson. Aquí, para una familia de subconjuntos de un conjunto finito , una base fija para es otra familia de subconjuntos de , de modo que cada conjunto puede describirse como la unión de algunos elementos básicos de . El problema de la base establecida ahora se da de la siguiente manera:
- INSTANCIA: Un conjunto finito , una familia de subconjuntos de y un entero positivo k .
- PREGUNTA: ¿Existe una base establecida de tamaño como máximo? por ?
En su antigua formulación, el problema fue demostrado ser NP -Complete por Orlin (1977) , incluso para gráficos bipartitos . Stockmeyer (1975) demostró anteriormente que la formulación como un problema de base fija era NP -completa . El problema sigue siendo NP -hard incluso si limitamos nuestra atención a gráficos bipartitos cuya dimensión bipartita está garantizada como máximo, donde n denota el tamaño de la instancia de problema dada ( Gottlieb, Savage y Yerukhimovich 2005 ). En el lado positivo, el problema se puede resolver en tiempo polinomial en gráficos bipartitos sin dominó ( Amilhastre, Janssen & Vilarem 1997 ).
En cuanto a la existencia de algoritmos de aproximación , Simon (1990) demostró que el problema no se puede aproximar bien (asumiendo P ≠ NP ). De hecho, la dimensión bipartita es NP -difícil de aproximar dentro de por cada fijo , ya para gráficos bipartitos ( Gruber & Holzer 2007 ).
Por el contrario, demostrar que el problema es manejable con parámetros fijos es un ejercicio de diseño de algoritmos de kernelización , que aparece como tal en el libro de texto de Downey & Fellows (1999) . Fleischner y col. (2009) también proporcionan un límite concreto sobre el tamaño del grano resultante, que mientras tanto ha sido mejorado por Nor et al. (2010) . De hecho, para un gráfico bipartito dado en n vértices, se puede decidir a tiempo con si su dimensión bipartita es como máximo k ( Nor et al.2010 )
Aplicaciones
El problema de determinar la dimensión bipartita de un gráfico aparece en varios contextos de la informática. Por ejemplo, en los sistemas informáticos, se puede permitir o no permitir a diferentes usuarios de un sistema el acceso a varios recursos. En un sistema de control de acceso basado en roles , un rol proporciona derechos de acceso a un conjunto de recursos. Un usuario puede poseer múltiples roles y tiene permiso para acceder a todos los recursos otorgados por algunos de sus roles. Además, un rol puede ser propiedad de varios usuarios. El problema de la minería de roles es encontrar un conjunto mínimo de roles, de modo que para cada usuario, sus roles tomados en conjunto otorguen acceso a todos los recursos especificados. El conjunto de usuarios junto con el conjunto de recursos en el sistema induce naturalmente un grafo bipartito, cuyos bordes son permisos. Cada biclicua en este gráfico es un rol potencial, y las soluciones óptimas para el problema de la minería de roles son precisamente las cubiertas de borde biclique mínimas ( Ene et al. 2008 ).
Un escenario similar se conoce en la seguridad informática , más específicamente en la radiodifusión segura . En esa configuración, es necesario enviar varios mensajes cada uno a un conjunto de receptores, a través de un canal inseguro. Cada mensaje tiene que estar encriptado usando alguna clave criptográfica que sea conocida solo por los destinatarios previstos. Cada receptor puede poseer varias claves de cifrado y cada clave se distribuirá a varios receptores. El problema óptimo de generación de claves es encontrar un conjunto mínimo de claves de cifrado para garantizar una transmisión segura. Como se indicó anteriormente, el problema se puede modelar utilizando un gráfico bipartito cuyas cubiertas de borde biclicuas mínimas coinciden con las soluciones al problema de generación de claves óptimas ( Shu, Lee & Yannakakis 2006 ).
Una aplicación diferente radica en la biología, donde se utilizan cubiertas de borde biclicuas mínimas en modelos matemáticos de serología de antígeno leucocitario humano (HLA) ( Nau et al. 1978 ).
Ver también
- Lista de problemas NP-completos
- Número de intersección (teoría de grafos) , el número mínimo de grupos necesarios para cubrir los bordes de un gráfico
Referencias
- Amilhastre, Jérôme; Janssen, Philippe; Vilarem, Marie-Catherine (1997), "Calcular una cobertura mínima biclicua es polinomio para gráficos bipartitos libres de dominó", Actas del Octavo Simposio Anual ACM-SIAM sobre Algoritmos Discretos, 5-7 de enero de 1997, Nueva Orleans, Luisiana. , ACM / SIAM, págs. 36–42
- de Caen, Dominique; Gregory, David A .; Pullman, Norman J. (1981), "The Boolean rank of zero-one matrices", en Cadogan, Charles C. (ed.), 3rd Caribbean Conference on Combinatorics and Computing , Departamento de Matemáticas, Universidad de las Indias Occidentales, págs. 169-173 , MR 0657202.
- Downey, Rod ; Becarios, Michael R. (1999), complejidad parametrizada , Springer, ISBN 0-387-94883-X.
- Ene, Alina; Horne, William G .; Milosavljevic, Nikola; Rao, Prasad; Schreiber, Robert; Tarjan, Robert Endre (2008), "Métodos rápidos, exactos y heurísticos para problemas de minimización de roles", en Ray, Indrakshi; Li, Ninghui (eds.), 13 ° Simposio de ACM sobre modelos y tecnologías de control de acceso (SACMAT 2008) , ACM, págs. 1-10.
- Fishburn, Peter C .; Hammer, Peter Ladislaw (1996), "Dimensiones bipartitas y grados bipartitos de gráficos", Matemáticas discretas , 160 (1–3): 127–148, doi : 10.1016 / 0012-365X (95) 00154-O.
- Fleischner, Herbert; Mujuni, Egbert; Paulusma, Daniël; Szeider, Stefan (2009), "Cubriendo gráficos con pocos subgrafos bipartitos completos", Informática teórica , 410 (21-23): 2045-2053, doi : 10.1016 / j.tcs.2008.12.059.
- Garey, Michael R .; Johnson, David S. (1979), Computadoras e intratabilidad: una guía para la teoría de NP-Completeness , WH Freeman, ISBN 0-7167-1045-5.
- Gottlieb, Lee-Ad J .; Savage, John E .; Yerukhimovich, Arkady (2005), "Almacenamiento de datos eficiente en grandes nanoarrays", Theory of Computing Systems , 38 (4): 503–536, doi : 10.1007 / s00224-004-1196-9.
- Gruber, Hermann; Holzer, Markus (2007), "Inaproximabilidad del estado no determinista y la complejidad de la transición asumiendo P <> NP", en Harju, Terjo; Karhumäki, Juhani; Lepistö, Arto (eds.), 11a Conferencia Internacional sobre Desarrollos en la Teoría del Lenguaje (DLT 2007) , LNCS, 4588 , Turku, Finlandia: Springer, págs. 205–216, doi : 10.1007 / 978-3-540-73208-2_21.
- Guo, Krystal; Huynh, Tony; Macchia, Marco (2019), "The Biclique Covering Number of Grids", The Electronic Journal of Combinatorics , 26 (4), doi : 10.37236 / 8316.
- Monson, Sylvia D .; Pullman, Norman J .; Rees, Rolf (1995), "Un estudio de recubrimientos de camarillas y biclices y factorizaciones de (0,1) -matrices", Boletín de la ICA , 14 : 17–86, MR 1330781.
- Nau, DS; Markowsky, G .; Woodbury, MA; Amos, DB (1978), "Un análisis matemático de la serología del antígeno leucocitario humano" (PDF) , Biociencias matemáticas , 40 (3–4): 243–270, doi : 10.1016 / 0025-5564 (78) 90088-3.
- Tampoco Igor; Hermelin, Danny; Charlat, Sylvain; Engelstadter, Jan; Reuter, Max; Duron, Olivier; Sagot, Marie-France (2010), "Mod / Resc Parsimony Inference", Combinatorial Pattern Matching , Lecture Notes in Computer Science, 6129 , pp. 202-213, arXiv : 1002.1292 , doi : 10.1007 / 978-3-642-13509 -5_19 , ISBN 978-3-642-13508-8
- Orlin, James (1977), "Satisfacción en la teoría de grafos: cubriendo grafos con camarillas", Indagationes Mathematicae , 80 (5): 406–424, doi : 10.1016 / 1385-7258 (77) 90055-5.
- Shu, Guoqiang; Lee, David; Yannakakis, Mihalis (2006), "Una nota sobre la gestión de claves de cifrado de difusión con aplicaciones para sistemas de alerta de emergencia a gran escala", 20º Simposio internacional de procesamiento paralelo y distribuido (IPDPS 2006) , IEEE.
- Simon, Hans-Ulrich (1990), "Sobre soluciones aproximadas para problemas de optimización combinatoria", SIAM Journal on Discrete Mathematics , 3 (2): 294–310, doi : 10.1137 / 0403025.
- Stockmeyer, Larry J. (1975), El problema de la base establecida es NP-completo , Informe técnico RC-5431, IBM.
enlaces externos
- entrada de blog sobre la dimensión bipartita de David Eppstein