Dimensión bipartita

En teoría de grafos y optimización combinatoria , la dimensión bipartita o el 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 de E. El conjunto de bicliques que cubren todas las aristas en G se denomina arista biclique cover , o simplemente biclique cover . La dimensión bipartita de un gráfico G a menudo se denota con el símbolo d ( G ).

Ejemplo

En los siguientes diagramas se muestra un ejemplo de cobertura de bordes con dos clics:

Un ejemplo de cobertura de bordes con bicliques
Gráfica bipartita...
...y cubriendo la gráfica con cuatro bicliques
funda biclika roja
funda biclick azul
tapa biclick verde
funda biclick negra

Fórmulas de dimensión bipartita para algunos gráficos

La dimensión biclique de un grafo completo con n vértices es . $K_n$ $\lceil \log _{2}n\rceil$

La dimensión bipartita de una corona con 2n vértices es , donde $\sigma(n)$

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

es la función inversa del coeficiente binomial central [1] . Fishburne y Hammer [2] definieron dimensiones bipartitas para algunos gráficos especiales. Por ejemplo, una ruta tiene una dimensión de , mientras que un bucle tiene una dimensión de . $P_{n}$ $d(P_{n})=\lpiso n/2\rpiso$ $C_{n}$ $d(C_{n})=\lceil n/2\rceil$

Cálculo de dimensiones bipartitas

El problema de determinar la dimensión bipartita para un gráfico G dado es un problema de optimización . El problema de solución para la dimensión bipartita se puede reformular de la siguiente manera:

DADO: Una gráfica y un entero positivo .

G=(V,E)

k

PREGUNTA: ¿G contiene un recubrimiento biclique de aristas con un máximo biclique?

k

Este problema está contenido bajo el número GT18 en el libro clásico sobre NP -completitud de Garey y Johnson [3] y es una reformulación directa de otro problema de resolubilidad sobre familias de conjuntos finitos.

El problema básico de conjuntos está contenido bajo el número SP7 en el mismo libro. Aquí se nos da una familia de subconjuntos de un conjunto finito , el conjunto básico de es otra familia de subconjuntos del conjunto , de manera que cualquier conjunto de puede representarse como la unión de algunos elementos básicos de . El problema básico del conjunto se formula ahora de la siguiente manera: ${\mathcal {S}}=\{S_{1},\ldots,S_{n}}\}$ ${\ matemáticas {U}}$ $\mathcal{S}$ ${\mathcal {B}}=\{B_{1},\ldots,B_{\ell }\}$ ${\ matemáticas {U}}$ $Si}$ ${\ matemáticas {B}}$

DADO: Un conjunto finito , una familia de subconjuntos del conjunto y un entero positivo k .

{\ matemáticas {U}}

{\mathcal {S}}=\{S_{1},\ldots,S_{n}}\}

{\ matemáticas {U}}

PREGUNTA: ¿Existe un conjunto base para el cual el tamaño es como máximo ?

\mathcal{S}

k

En la primera formulación, Orlin [4] demostró la completitud de NP incluso para grafos bipartitos . La completitud NP del problema de conjuntos básicos fue demostrada anteriormente por Stockmeyer [5] . El problema sigue siendo NP -hard incluso si nos restringimos a grafos bipartitos cuya dimensión bipartita no exceda , donde n denota el tamaño de un problema particular [6] . Sin embargo, es bueno que el problema se pueda resolver en tiempo polinomial en gráficos bipartitos sin dominó [7] (un dominó es una escalera de altura 3). ${\ estilo de visualización O (\ registro \, \! n)}$

En cuanto a la existencia de algoritmos de aproximación, Simon [8] demostró que el problema no se puede aproximar bien (asumiendo P ≠ NP ). Además, la dimensión bipartita es NP -difícil de aproximar para cualquier gráfico fijo incluso para bipartito [9] . $|V|^{1/3-\epsilon}$ ${\ estilo de visualización \ épsilon > 0}$

En comparación, demostrar que un problema tiene solución paramétrica fija es un ejercicio de construcción de algoritmos de reducción paramétrica (como en el libro de Donway y Fellows [10] ). Fleischner, Mijuni, Paulusma y Seider [11] también dieron límites específicos al kernel resultante, que mientras tanto fueron mejorados por Nohr, Hermelin, Charlat y otros [12] .

De hecho, para un grafo bipartito dado con n vértices, se puede determinar en el tiempo , donde , si la dimensión bipartita del grafo del número k es mayor o no [12] . ${\ Displaystyle O (f (k)) + n ^ {3))$ ${\displaystyle f(k)=2^{k2^{k-1}+3k))$

Aplicación

El problema de determinar la dimensión bipartita de un gráfico surge en varios contextos computacionales. Por ejemplo, en los sistemas informáticos, a diferentes usuarios del sistema se les puede permitir o denegar el acceso a varios recursos. En el control de acceso basado en funciones, la función de un usuario determina los derechos de acceso a un conjunto de recursos. Un usuario puede tener varios roles y puede acceder a los recursos disponibles para uno de los roles. Un rol, a su vez, se puede asignar a múltiples usuarios. La tarea de buscar roles es asignar un conjunto mínimo de roles que para cada usuario, los roles asignados a él garanticen el acceso a todos los recursos que el usuario necesita. El conjunto de usuarios, junto con el conjunto de recursos, define naturalmente un grafo bipartito cuyos bordes definen el acceso de los usuarios a los recursos. Cada biclique en dicho gráfico es un rol potencial, y la solución óptima al problema de encontrar roles es exactamente la cobertura mínima de borde por bicliques [13] .

Un escenario similar ocurre en la seguridad informática , más específicamente en la transmisión segura . En esta situación, es necesario enviar algunos mensajes a varios receptores a través de un canal no seguro. Cada mensaje debe cifrarse con alguna clave de cifrado, que solo conoce el receptor al que se transmite el mensaje. Cada receptor puede tener muchas claves de cifrado y cada clave se envía a varios receptores. La tarea de elegir la opción óptima de claves de cifrado es encontrar el conjunto mínimo de claves de cifrado que garantizará una distribución segura. Como antes, el problema se puede modelar utilizando un gráfico bipartito en el que la cobertura de borde bi-clique mínima coincide con la solución al problema de elección óptima de claves de cifrado [14] .

Otra aplicación es en biología, donde la cobertura mínima de bordes por bicliques se usa en el modelado matemático del antígeno leucocitario humano (HLA) en serología [15] .

Véase también

Lista de problemas NP-completos
El número de intersecciones del gráfico , el número mínimo de camarillas requeridas para cubrir los bordes de los gráficos.

Notas

Literatura

Jérôme Amilhastre, Philippe Janssen, Marie-Catherine Vilarem. Actas del Octavo Simposio Anual ACM-SIAM sobre Algoritmos Discretos, 5-7 de enero de 1997, Nueva Orleans, Luisiana - ACM/SIAM, 1997. - P. 36-42.
Dominique de Caen, David A. Gregory, Norman J. Pullman. 3ra Conferencia Caribeña de Combinatoria y Computación / Charles C. Cadogan. - Departamento de Matemáticas, Universidad de las Indias Occidentales, 1981. - S. 169-173.
Rod Downey, Michael R. Fellows. Complejidad parametrizada. - Springer, 1999. - ISBN 0-387-94883-X .
Alina Ene, William G. Horne, Nikola Milosavljevic, Prasad Rao, Robert Schreiber, Robert Endre Tarjan. 13° Simposio ACM sobre Modelos y Tecnologías de Control de Acceso (SACMAT 2008) / Indrakshi Ray, Ninghui Li. - ACM, 2008. - S. 1–10.
Peter C. Fishburn, Peter Ladislaw Hammer. Dimensiones bipartitas y grados bipartitos de grafos // Matemáticas discretas . - 1996. - T. 160 , núm. 1–3 . — págs. 127–148 . - doi : 10.1016/0012-365X(95)00154-O .
Herbert Fleischner, Egbert Mujuni, Daniël Paulusma, Stefan Szeider. Cubriendo gráficos con pocos subgrafos bipartitos completos // Ciencias de la Computación Teórica . - 2009. - T. 410 , núm. 21-23 . — S. 2045–2053 . -doi : 10.1016/ j.tcs.2008.12.059 .
Michael R. Garey, David S. Johnson. Computadoras e intratabilidad: una guía para la teoría de la integridad NP . - WH Freeman, 1979. - ISBN 0-7167-1045-5 .
Lee-Ad J. Gottlieb, John E. Savage, Arkady Yerukhimovich. Almacenamiento eficiente de datos en grandes nanoarreglos // Teoría de los Sistemas Computacionales. - 2005. - T. 38 , núm. 4 . — S. 503–536 . -doi : 10.1007/ s00224-004-1196-9 .
Hermann Gruber, Markus Holzer. 11ª Conferencia Internacional sobre Desarrollos en Teoría del Lenguaje (DLT 2007) / Terjo Harju, Juhani Karhumäki, Arto Lepistö. - Turku, Finlandia: Springer, 2007. - T. 4588. - S. 205-216. — (LNCS). -doi : 10.1007 / 978-3-540-73208-2_21 .
Sylvia D. Monson, Norman J. Pullman, Rolf Rees. Una encuesta de coberturas clique y biclique y factorizaciones de (0,1)-matrices // Bulletin of the ICA. - 1995. - T. 14 . — P. 17–86 .
DS Nau, G. Markowsky, MA Woodbury, DB Amos. Un análisis matemático de la serología del antígeno leucocitario humano // Biociencias matemáticas. - 1978. - T. 40 . — S. 243–270 . - doi : 10.1016/0025-5564(78)90088-3 .
Igor Nor, Danny Hermelin, Sylvain Charlat, Jan Engelstadter, Max Reuter, Olivier Duron, Marie-France Sagot. Inferencia de parsimonia Mod/Resc . — 2010.
James Orlín. Satisfacción en la teoría de grafos: cubriendo grafos con camarillas // Indagationes Mathematicae . - 1977. - T. 80 , núm. 5 . — S. 406–424 . - doi : 10.1016/1385-7258(77)90055-5 .
Guoqiang Shu, David Lee, Mihalis Yannakakis. 20º Simposio Internacional de Procesamiento Paralelo y Distribuido (IPDPS 2006). —IEEE, 2006.
Hans Ulrich Simon. Sobre soluciones aproximadas para problemas de optimización combinatoria // SIAM Journal on Discrete Mathematics . - 1990. - T. 3 , nº. 2 . — S. 294–310 . -doi : 10.1137/ 0403025 .

Enlaces

Artículo sobre Dimensión Bipartita de David Eppstein