Dimensión bipartita

En los campos matemáticos de la teoría de grafos y la optimización combinatoria , la dimensión bipartita o número de cobertura biclique de un gráfico G  = ( V ,  E ) es el número mínimo de bicliques (es decir, subgrafos bipartitos completos), necesarios para cubrir todos los bordes en E. Una colección de bicliques que cubren todos los bordes en G se llama cobertura de borde biclique o, a veces, cobertura biclique . La dimensión bipartita de G a menudo se denota con el símbolo d ( G ).

Ejemplo

En los siguientes diagramas se ofrece un ejemplo de cubierta de borde biclique:

• Ejemplo de cobertura de borde biclique
• 
  Un gráfico bipartito...
• 
  ...y una cubierta con cuatro bicliques
• 
  la biclique roja de la portada
• 
  la bicicleta azul de la portada
• 
  la biclique verde de la portada
• 
  la biclique negra 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 . ${\displaystyle K_{n}}$ ${\displaystyle \lceil \log _{2}n\rceil }$

La dimensión bipartita de un gráfico de corona de 2n vértices es igual a , donde ${\displaystyle \sigma (n)}$

${\displaystyle \sigma (n)=\min \left\{\,k\mid n\leq {\binom {k}{\lfloor k/2\rfloor }}\,\right\}}$

es la función inversa del coeficiente binomial central (de Caen, Gregory y Pullman 1981).

La dimensión bipartita del gráfico reticular es , si es par y para algunos números enteros ; y es diferente (Guo, Huynh & Macchia 2019). ${\displaystyle n\times m}$ ${\displaystyle {\frac {nm}{2}}-1}$ ${\displaystyle m}$ ${\displaystyle n-1=k(m-1)+2\ell }$ ${\displaystyle 0\leq \ell <k}$ ${\displaystyle {\big \lfloor }{\frac {nm}{2}}{\big \rfloor }}$

Fishburn y Hammer (1996) determinan la dimensión bipartita para algunos gráficos especiales. Por ejemplo, la ruta tiene y el ciclo tiene . ${\displaystyle P_{n}}$ ${\displaystyle d(P_{n})=\lfloor n/2\rfloor }$ ${\displaystyle C_{n}}$ ${\displaystyle d(C_{n})=\lceil n/2\rceil }$

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 se puede formular como:

INSTANCIA: Una gráfica y un entero positivo . ${\displaystyle G=(V,E)}$ ${\displaystyle k}$

PREGUNTA: ¿G admite una cubierta de borde biclique que contenga como máximo bicliques? ${\displaystyle k}$

Este problema aparece como problema GT18 en el libro clásico de Garey y Johnson sobre completitud NP , 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 problema SP7 en el libro de Garey y Johnson. Aquí, para una familia de subconjuntos de un conjunto finito , un conjunto base 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 base establecida ahora se plantea de la siguiente manera: ${\displaystyle {\mathcal {S}}=\{S_{1},\ldots ,S_{n}\}}$ ${\displaystyle {\mathcal {U}}}$ ${\displaystyle {\mathcal {S}}}$ ${\displaystyle {\mathcal {B}}=\{B_{1},\ldots ,B_{\ell }\}}$ ${\displaystyle {\mathcal {U}}}$ ${\displaystyle S_{i}}$ ${\displaystyle {\mathcal {B}}}$

INSTANCIA: Un conjunto finito , una familia de subconjuntos de y un entero positivo k . ${\displaystyle {\mathcal {U}}}$ ${\displaystyle {\mathcal {S}}=\{S_{1},\ldots ,S_{n}\}}$ ${\displaystyle {\mathcal {U}}}$

PREGUNTA: ¿Existe una base establecida de tamaño como máximo para ? ${\displaystyle k}$ ${\displaystyle {\mathcal {S}}}$

En su formulación anterior, Orlin (1977) demostró que el problema era NP -completo , 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 -difícil incluso si restringimos nuestra atención a grafos bipartitos cuya dimensión bipartita está garantizada como máximo , donde n denota el tamaño de la instancia del problema dada (Gottlieb, Savage y Yerukhimovich 2005). En el lado positivo, el problema se puede resolver en tiempo polinomial en gráficos bipartitos libres de dominó (Amilhastre, Janssen y Vilarem 1997). ${\displaystyle O(\log \,\!n)}$

Respecto a la existencia de algoritmos de aproximación , Simon (1990) demostró que el problema no puede aproximarse bien (asumiendo P  ≠  NP ). De hecho, la dimensión bipartita es NP , difícil de aproximar para cada gráfico bipartito (Gruber y Holzer 2007). ${\displaystyle |V|^{1/3-\epsilon }}$ ${\displaystyle \epsilon >0}$

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 y Fellows (1999). Fleischner et al. (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 si su dimensión bipartita es como máximo k (Nor et al. 2010) ${\displaystyle O(f(k))+n^{3}}$ ${\displaystyle f(k)=2^{k2^{k-1}+3k}}$

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, a diferentes usuarios de un sistema se les puede permitir o no el acceso a diversos 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 manera que para cada usuario, sus roles en conjunto otorguen acceso a todos los recursos especificados. El conjunto de usuarios junto con el conjunto de recursos del sistema induce naturalmente un grafo bipartito, cuyos bordes son los permisos. Cada biclique en este gráfico es un rol potencial, y las soluciones óptimas al problema de minería de roles son precisamente las coberturas mínimas de bordes de biclique (Ene et al. 2008).

Un escenario similar se conoce en el ámbito de la seguridad informática , más concretamente en la radiodifusión segura . En esa configuración, es necesario enviar varios mensajes, cada uno de ellos a un conjunto de receptores, a través de un canal inseguro. Cada mensaje debe cifrarse utilizando alguna clave criptográfica que sólo conozcan los destinatarios previstos. Cada receptor puede poseer múltiples claves de cifrado y cada clave se distribuirá a múltiples receptores. El problema de generación de claves óptima 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 coberturas mínimas de bordes bicliques coinciden con las soluciones al problema de generación de claves óptimas (Shu, Lee y Yannakakis 2006).

Una aplicación diferente reside en la biología, donde se utilizan cubiertas de borde biclique mínimo en modelos matemáticos de serología del 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 camarillas necesarias para cubrir los bordes de un gráfico.

Referencias

• Amilhastre, Jérôme; Janssen, Philippe; Vilarem, Marie-Catherine (1997), "Calcular una cobertura biclique mínima es polinomio para gráficos bipartitos sin dominó", Actas del octavo simposio anual ACM-SIAM sobre algoritmos discretos, 5 a 7 de enero de 1997, Nueva Orleans, Luisiana. ACM/SIAM, págs. 36–42, ISBN 9780898713909
• de Caen, Dominique; Gregorio, David A.; Pullman, Norman J. (1981), "The Boolean Rank of Zero-One Matrixs", en Cadogan, Charles C. (ed.), Tercera Conferencia del Caribe sobre Combinatoria y Computación , Departamento de Matemáticas, Universidad de las Indias Occidentales, págs. 169–173, SEÑOR  0657202..
• Downey, varilla ; Fellows, 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 heurísticos y exactos rápidos para problemas de minimización de roles", en Ray, Indrakshi; Li, Ninghui (eds.), 13º Simposio ACM sobre modelos y tecnologías de control de acceso (SACMAT 2008) , ACM, págs..
• Fishburn, Peter C .; Hammer, Peter Ladislaw (1996), "Dimensiones bipartitas y grados bipartitos de gráficas", Matemáticas discretas , 160 (1–3): 127–148, doi : 10.1016/0012-365X(95)00154-O.
• Fleischner, Herbert; Mujuni, Egbert; Paulusma, Daniel; Szeider, Stefan (2009), "Cubre gráficos con algunos subgrafos bipartitos completos", Ciencias de la Computación 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 la integridad NP , WH Freeman, ISBN 0-7167-1045-5.
• Gottlieb, Lee-Ad J.; Salvaje, John E .; Yerukhimovich, Arkady (2005), "Almacenamiento de datos eficiente en grandes nanoarrays", Teoría de los sistemas informáticos , 38 (4): 503–536, doi :10.1007/s00224-004-1196-9, S2CID  5844939.
• Gruber, Hermann; Holzer, Markus (2007), "Inaproximabilidad del estado no determinista y complejidad de la transición suponiendo P <> NP", en Harju, Terjo; Karhumäki, Juhani; Lepistö, Arto (eds.), 11ª Conferencia Internacional sobre Desarrollos en la Teoría del Lenguaje (DLT 2007) , LNCS, vol. 4588, Turku, Finlandia: Springer, págs. 205–216, doi :10.1007/978-3-540-73208-2_21.
• Guo, Krystal; Huynh, Tony; Macchia, Marco (2019), "La Biclique que cubre el número de cuadrículas", The Electronic Journal of Combinatorics , 26 (4), arXiv : 1811.03396 , doi : 10.37236/8316.
• Monson, Sylvia D.; Pullman, Norman J.; Rees, Rolf (1995), "Un estudio de coberturas y factorizaciones de camarillas y bicliques de (0,1) -matrices", Boletín del 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) , Mathematical Biosciences , 40 (3–4): 243–270, doi :10.1016/0025-5564(78)90088-3.
• Tampoco, Ígor; Hermelín, Danny; Charlat, Sylvain; Engelstadter, enero; Reuters, Max; Durón, Olivier; Sagot, Marie-France (2010), "Inferencia de parsimonia Mod/Resc", Coincidencia de patrones combinatorios , Apuntes de conferencias sobre informática, vol. 6129, págs. 202–213, arXiv : 1002.1292 , doi : 10.1007/978-3-642-13509-5_19, ISBN 978-3-642-13508-8, S2CID  6675399
• Orlin, James (1977), "Contenido en la teoría de grafos: cubrir gráficos 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 transmisión con aplicaciones a sistemas de alerta de emergencia a gran escala", 20º Simposio internacional de procesamiento distribuido y paralelo (IPDPS 2006) , IEEE.
• Simon, Hans-Ulrich (1990), "Sobre soluciones aproximadas para problemas de optimización combinatoria", Revista SIAM de matemáticas discretas , 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 por David Eppstein