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 recubrimiento biclicuo de un grafo G  = ( V ,  E ) es el número mínimo de biclicuos (es decir, subgrafos bipartitos completos), necesarios para cubrir todas las aristas en E . Una colección de biclicuos que cubren todas las aristas en G se denomina recubrimiento de arista biclicuo , o a veces recubrimiento biclicuo . 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 biclicuo:

• Ejemplo de cubierta de borde biclique
• 
  Un gráfico bipartito...
• 
  ...y una cubierta con cuatro bicliques
• 
  La biclique roja de la portada
• 
  La biclique 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 grafo 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 en caso contrario (Guo, Huynh y 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 de algunos grafos 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 }$

Cálculo de la dimensión bipartita

La tarea computacional de determinar la dimensión bipartita para un grafo G dado es un problema de optimización . El problema de decisión para la dimensión bipartita se puede formular de la siguiente manera:

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

PREGUNTA: ¿Admite G una cubierta de aristas biclícuas que contenga como máximo aristas biclícuas? ${\displaystyle k}$

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 de conjuntos aparece como problema SP7 en el libro de Garey y Johnson. Aquí, para una familia de subconjuntos de un conjunto finito , una base de conjuntos para es otra familia de subconjuntos de , de modo que cada conjunto puede describirse como la unión de algunos elementos de base de . El problema de la base de conjuntos ahora se da 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 fija 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 grafos bipartitos . Stockmeyer (1975) demostró anteriormente que la formulación como un problema de base de conjuntos era NP -completo. 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 grafos 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 se puede aproximar bien (suponiendo que P  ≠  NP ). De hecho, la dimensión bipartita es NP -difícil de aproximar dentro de cada , fijo , incluso para grafos bipartitos (Gruber & 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 & Fellows (1999). Fleischner et al. (2009) también proporcionan un límite concreto para el tamaño del kernel resultante, que entretanto ha sido mejorado por Nor et al. (2010). De hecho, para un grafo bipartito dado en n vértices, se puede decidir en el 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 grafo aparece en varios contextos de computación. Por ejemplo, en los sistemas informáticos, a diferentes usuarios de un sistema se les puede permitir o denegar 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 múltiples usuarios. El problema de minería de roles consiste en 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 biclique en este grafo es un rol potencial, y las soluciones óptimas para el problema de minería de roles son precisamente las coberturas mínimas de bordes bicliques (Ene et al. 2008).

Un escenario similar se conoce en seguridad informática , más específicamente en transmisión segura . En esa configuración, se deben enviar varios mensajes, cada uno a un conjunto de receptores, a través de un canal inseguro. Cada mensaje debe cifrarse utilizando una clave criptográfica que solo conocen los receptores 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 óptimas es encontrar un conjunto mínimo de claves de cifrado para garantizar una transmisión segura. Como se mencionó anteriormente, el problema se puede modelar utilizando un gráfico bipartito cuyas coberturas de aristas bicliques mínimas coinciden con las soluciones al problema de generación de claves óptimas (Shu, Lee y Yannakakis 2006).

Una aplicación diferente se encuentra en biología, donde se utilizan cubiertas de bordes bicliques mínimos en modelos matemáticos de serología del antígeno leucocitario humano (HLA) (Nau et al. 1978).

Véase 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 grafo

Referencias

• Amilhastre, Jérôme; Janssen, Philippe; Vilarem, Marie-Catherine (1997), "El cálculo de una cobertura biclique mínima es polinomial para grafos bipartitos sin 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, ISBN 9780898713909
• de Caen, Dominique; Gregory, David A.; Pullman, Norman J. (1981), "El rango booleano de matrices cero-uno", 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 ; 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 rápidos, exactos y heurísticos para problemas de minimización de roles", en Ray, Indrakshi; Li, Ninghui (eds.), 13.º Simposio de la 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 grafos", Discrete Mathematics , 160 (1–3): 127–148, doi : 10.1016/0012-365X(95)00154-O.
• Fleischner, Herbert; Mujuni, Egbert; Paulusma, Daniël; Szeider, Stefan (2009), "Cobertura de gráficos con pocos subgráficos bipartitos completos", Theoretical Computer Science , 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 NP-completitud , WH Freeman, ISBN 0-7167-1045-5.
• Gottlieb, Lee-Ad J.; Savage, John E .; Yerukhimovich, Arkady (2005), "Almacenamiento eficiente de datos en nanoarreglos grandes", Theory of Computing Systems , 38 (4): 503–536, doi :10.1007/s00224-004-1196-9, S2CID  5844939.
• Gruber, Hermann; Holzer, Markus (2007), "Inaproximabilidad de estados no deterministas y complejidad de transición suponiendo P <> NP.", en Harju, Terjo; Karhumäki, Juhani; Lepistö, Arto (eds.), 11.ª Conferencia internacional sobre desarrollos en 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, ISBN 978-3-540-73207-5.
• Guo, Krystal; Huynh, Tony; Macchia, Marco (2019), "El número de cuadrículas que cubren la biclique", 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 recubrimientos clique y biclique y factorizaciones de matrices (0,1)", 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) , Mathematical Biosciences , 40 (3–4): 243–270, doi :10.1016/0025-5564(78)90088-3.
• Nor, 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, vol. 6129, págs. 202–213, arXiv : 1002.1292 , doi :10.1007/978-3-642-13509-5_19, ISBN 978-3-642-13508-8, Número de identificación del sujeto  6675399
• Orlin, James (1977), "Conformidad 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 a sistemas de alerta de emergencia a gran escala", 20.º Simposio internacional sobre procesamiento paralelo y distribuido (IPDPS 2006) , IEEE.
• Simon, Hans-Ulrich (1990), "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 de conjuntos es NP-completo , Informe técnico RC-5431, IBM.

Enlaces externos

• Entrada de blog sobre la dimensión bipartita de David Eppstein