Dimensión bipartita

En los campos matemáticos de teoría de grafos y optimización combinatotria, la dimensión bipartita, o número de cubierta de bicliques de un grafo $G(V,E)$ es el número mínimo de bicliques (es decir, subgrafos bipartitos completos), que se necesitan para cubrir todas las aristas en $E$. Decimos que una colección de bicliques cubriendo todas las aristas en $G$ es una cubierta de aristas de bicliques, o a veces covertura biclique. La dimensión bipartira de G es a menudo denotada por el símbolo $d(G)$.

Ejemplo

Un ejemplo para un cubierta de aristas biclique está dada en las siguientes figuras:

• 
  Un grafo bipartito...
• 
  ...y una cubierta con cuatro bicliques.
• 
  la biclique roja;
• 
  la biclique azul;
• 
  la biclique verde;
• 
  y la biclique negra;

Fórmulas de dimensión bipartita para algunos grafos

La dimensión bipartita del grafo completo en n vértices, es .$K_n$$\lceil {\log }_{2}n\rceil$

La dimensión bipartira de un grafo de corona con $2n$vértices es $\sigma (n)$, donde

$\sigma (n)=\min \{k\mid n\le (\genfrac{}{}{0ex}{}{k}{\lfloor k/2\rfloor })\}$

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

La dimensión bipartita del grafo de celosía de $n\times m$es $\frac{nm}{2}-1$

, $m$ si par y $n-1=k(m-1)+2\ell$ para algunos enteros $0\le \ell <k$; y de otro modo, es $\lfloor \frac{nm}{2}\rfloor$(Guo, Huynh & Macchia 2019).

Plantilla:Harvtxt determinaron la dimensión bipartita para algunos grafos especiales. Por ejemplo, el camino $P_n$ tiene $d(P_n)=\lfloor n/2\rfloor$ y el ciclo $C_n$ tiene $d(C_n)=\lceil n/2\rceil$.

Computando la dimensión bipartita

La tarea computacional de determinar la dimensión bipartita de un grafo dado $G$ es un problema de optimización . El problema de decisión correspondiente puede ser fraseado como sigue:

INSTANCIA: Un grafo $G=(V,E)$ y un entero positivo $k$.

PREGUNTA: El grafo $G$ admite una cubierta biclique de arista que contiene como sumo $k$ bicliques?

Este problema aparece como el problema GT18 en el libro clásico de Garey y Johnson en completitud-NP, y es una reformulación bastante directa de otro problema de decisión en familias de conjuntos finitos.

El problema de base del conjunto aparece como problema SP7 en el libro de Garey y Johnson. Aquí, para una familia $𝒮=\{S_1,\dots ,S_n\}$ de subconjuntos de un conjunto finito $𝒰$, una base de conjunto para $𝒮$ es otra familia de subconjuntos $ℬ=\{B_1,\dots ,B_{\ell }\}$ de $𝒰$, tal que cada conjunto $S_i$ puede ser descrito como la unión de algunos elementos de la base $ℬ$. El problema de base del conjunto consiste en lo que sigue:

INSTANCIA: Un conjunto finito $𝒰$, una familia $𝒮=\{S_1,\dots ,S_n\}$ de subconjuntos de $𝒰$, y un entero positivo k.

PREGUNTA: Existe una base de conjunto para $𝒮$ de tamaño como máximo $k$?

En su formulación anterior, el problema fue probado ser NP-completo por Orlin (1977), incluso para grafos bipartitos. La formulación como problema de base de conjunto fue demostrada ser NP-completa anteriormente por Stockmeyer (1975). El problema sigue siendo NP-difícil incluso si restringimos nuestra atención a grafos bipartitos cuya dimensión bipartita sea garantizada como máximo $O(\log n)$, donde $n$ denota el tamaño de la instancia del problema (Gottlieb, Savage & Yerukhimovich 2005). Del lado positivo, el problema es resoluble en tiempo polinomial en grafos bipartitos libres de dominó(Amilhastre, Janssen & Vilarem, 1997).

Con resecto a la existencia de algoritmos de aproximación, Simon (1990) probó que el problema no puede ser aproximado bien (suponiendo que $P\ne NP$; ver Clases de complejidad P y NP). De hecho, la dimensión bipartita es NP-difícil de aproximar en un rango $|V{|}^{1/3-ϵ}$ para cada $ϵ>0$ fijo, incluso para grafos bipartitos (Gruber & Holzer 2007).

En contraste, probar que el problema es tractable dado un parámetro fijo es un ejercicio en diseñar algoritmos de kernelización, el cual aparece como tal en el libro por Plantilla:Harvtxt Fleischner Et al. (2009) también da una cuota concreta en la medida del kernel resultante, el cual entretanto ha sido mejorado por Nor et al. (2010). De hecho, dado un grafo bipartito en $n$ vértices, es posible decidir en tiempo $O(f(k))+n^3$ con $f(k)=2^{k{2}^{k-1}+3k}$ si la dimensión bipartita de este grafo es como máximo $k$ (Nor et al. 2010)

Aplicaciones

El problema de determinar la dimensión bipartita de un grafo aparece en varios contextos de computación. Por ejemplo, en sistemas de comutación, distintos usuarios de un sistema pueden ser permitidos o privados del 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 roles múltiples, y tiene permiso para acceder todos los recursos garantizados por algunos de sus roles. Asimismo, un rol puede ser ocupado por múltiples usuarios. El problema de búsqueda de roles pide encontrar un conjunto mínimo de roles, tal que para cada usuario, sus roles juntos le garantizan acceso a todos los recursos especificados por el enunciado. El conjunto de usuarios, junto con el conjunto de recursos en el sistema naturalmente induce un grafo bipartito, cuyas aristas son permisos de acceso a recursos. Cada biclique en este grafo es un rol potencial a tomar por usuarios, y las soluciones óptimas al problema son precisamente aquellas dadas por las cubiertas mínimas de aristas por bicliques (Ene et al. 2008).

Un escenario similar es conocido en ciberseguridad, más específicamente en el campo de radiodifusión segura. En dicho escenario, varios mensajes deben ser enviados a un conjunto de escuchas, sobre un canal inseguro. Cada mensaje tiene que ser encriptado utilizando alguna clave cirptográfica la cual es conocida sólo para los destinatarios. Cada destinatario puede poseer llaves de encriptación múltiples, y cada llave será distribuida a múltiples destinatarios. El problema de generación de clave óptima pide encontrar un conjunto mínimo de llaves de encriptación para asegurar una transmisión segura. Como anteriormente, el problema puede ser modelado utilizando un grafo bipartito cuya mínima cubiertas biclique de arista coincide con las soluciones al problema de generación clave óptima (Shu, Lee & Yannakakis 2006).

Una aplicación diferente está en la biología, donde cubiertas de arista biclique minimales pueden ser utilizadas en modelos matemáticos de antígenos leucocitos humanos (HLA) serología (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 cliques que se necesita para cubrir todas las aristas de un grafo.

• Plantilla:Obra citada
• Plantilla:Obra citada.
• Plantilla:Obra citada.
• Plantilla:Obra citada.
• Plantilla:Obra citada.
• Plantilla:Obra citada.
• Plantilla:Obra citada.
• Plantilla:Obra citada.
• Plantilla:Obra citada.
• Plantilla:Obra citada.
• Plantilla:Obra citada.
• Plantilla:Obra citada.
• Plantilla:Obra citada
• Plantilla:Obra citada.
• Plantilla:Obra citada.
• Plantilla:Obra citada.
• Plantilla:Obra citada.

Enlaces externos

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