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 \left\{\,k\mid n\leq {\binom {k}{\lfloor k/2\rfloor }}\,\right\}

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\leq \ell <k$ ; y de otro modo, es ${\big \lfloor }{\frac {nm}{2}}{\big \rfloor }$ (Guo, Huynh & Macchia 2019).

Fishburn y Hammer (1996) 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 ${\mathcal {S}}=\{S_{1},\ldots ,S_{n}\}$ de subconjuntos de un conjunto finito ${\mathcal {U}}$ , una base de conjunto para ${\mathcal {S}}$ es otra familia de subconjuntos ${\mathcal {B}}=\{B_{1},\ldots ,B_{\ell }\}$ de ${\mathcal {U}}$ , tal que cada conjunto $S_{i}$ puede ser descrito como la unión de algunos elementos de la base ${\mathcal {B}}$ . El problema de base del conjunto consiste en lo que sigue:

INSTANCIA: Un conjunto finito

{\mathcal {U}}

, una familia

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

de subconjuntos de

{\mathcal {U}}

, y un entero positivo k.

PREGUNTA: Existe una base de conjunto para

{\mathcal {S}}

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\neq 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-\epsilon }$ para cada $\epsilon >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 Downey y Fellows (1999) 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^{k2^{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.

Amilhastre, Jérôme; Janssen, Philippe; Vilarem, Marie-Catherine (1997), «Computing a minimum biclique cover is polynomial for bipartite domino-free graphs», Proceedings of the Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, 5–7 January 1997, New Orleans, Louisiana., ACM/SIAM, pp. 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, Department of Mathematics, University of the West Indies, pp. 169-173 ..
Downey, Rod; Fellows, Michael R. (1999), Parameterized complexity, Springer, ISBN 0-387-94883-X ..
Ene, Alina; Horne, William G.; Milosavljevic, Nikola; Rao, Prasad; Schreiber, Robert; Tarjan, Robert Endre (2008), «Fast exact and heuristic methods for role minimization problems», en Ray, Indrakshi; Li, Ninghui, eds., 13th ACM Symposium on Access Control Models and Technologies (SACMAT 2008), ACM, pp. 1-10 ..
Fishburn, Peter C.; Hammer, Peter Ladislaw (1996), «Bipartite dimensions and bipartite degrees of graphs», 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), «Covering graphs with few complete bipartite subgraphs», Theoretical Computer Science 410 (21–23): 2045-2053, doi:10.1016/j.tcs.2008.12.059 ..
Garey, Michael R.; Johnson, David S. (1979), Computers and Intractability: A Guide to the Theory of NP-Completeness, W.H. Freeman, ISBN 0-7167-1045-5 ..
Gottlieb, Lee-Ad J.; Savage, John E.; Yerukhimovich, Arkady (2005), «Efficient data storage in large nanoarrays», Theory of Computing Systems 38 (4): 503-536, doi:10.1007/s00224-004-1196-9 ..
Gruber, Hermann; Holzer, Markus (2007), «Inapproximability of Nondeterministic State and Transition Complexity Assuming P <> NP.», en Harju, Terjo; Karhumäki, Juhani; Lepistö, eds., 11th International Conference on Developments in Language Theory (DLT 2007), LNCS 4588, Turku, Finland: Springer, pp. 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), «A survey of clique and biclique coverings and factorizations of (0,1)-matrices», Bulletin of the ICA 14: 17-86 ..
Nau, D. S.; Markowsky, G.; Woodbury, M. A.; Amos, D. B. (1978), «A mathematical analysis of human leukocyte antigen serology», 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 6129, pp. 202-213, ISBN 978-3-642-13508-8, doi:10.1007/978-3-642-13509-5_19 .
Orlin, James (1977), «Contentment in graph theory: covering graphs with cliques», Indagationes Mathematicae 80 (5): 406-424, doi:10.1016/1385-7258(77)90055-5 ..
Shu, Guoqiang; Lee, David; Yannakakis, Mihalis (2006), «A note on broadcast encryption key management with applications to large scale emergency alert systems.», 20th International Parallel and Distributed Processing Symposium (IPDPS 2006), IEEE ..
Simon, Hans-Ulrich (1990), «On Approximate Solutions for Combinatorial Optimization Problems», SIAM Journal on Discrete Mathematics 3 (2): 294-310, doi:10.1137/0403025 ..
Stockmeyer, Larry J. (1975), The set basis problem is NP-complete, Technical Report RC-5431, IBM ..

Enlaces externos

Entrada de blog sobre dimensión bipartita por David Eppstein