Ver el código de «Dimensión bipartita»


En los campos mat''e''máticos de [[teoría de grafos]] y [[Optimización combinatoria|optimización combinatotria]], la '''dimensión bipartita''', o  '''número de cubierta de bicliques''' de un [[grafo]] <math>G(V,E)</math> es el número mínimo de bicliques (es decir, subgrafos bipartitos completos), que se necesitan para cubrir todas las aristas en <math>E</math>. Decimos que una colección de [[Grafo bipartito completo|bicliques]] cubriendo todas las aristas en <math>G</math> 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 <math>d(G)</math>.

== Ejemplo ==
Un ejemplo para un cubierta de aristas biclique está dada en las siguientes figuras:<gallery>
Archivo:Bipartite-dimension-bipartite-graph.svg|Un grafo bipartito...
Archivo:Bipartite-dimension-biclique-cover.svg|...y una cubierta con cuatro bicliques.
Archivo:Bipartite-dimension-red-biclique.svg|la biclique roja;
Archivo:Bipartite-dimension-blue-biclique.svg|la biclique azul;
Archivo:Bipartite-dimension-green-biclique.svg|la biclique verde;
Archivo:Bipartite-dimension-black-biclique.svg|y la biclique negra;
</gallery>

== Fórmulas de dimensión bipartita para algunos grafos ==
La dimensión bipartita del [[grafo completo]] en ''n'' vértices,  es .<math>K_n</math><math>\lceil \log_2 n\rceil </math>

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

: <math>\sigma(n)=\min \left\{\,k \mid n \le \binom{k}{\lfloor k/2 \rfloor} \,\right\}</math>

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

La dimensión bipartita del  [[Gráfico de celosía|grafo de celosía]] de <math>n \times m</math>es 
<math>\frac{nm}{2} -1</math>

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

{{Harvtxt|Fishburn|Hammer|1996}} determinaron la dimensión bipartita para algunos grafos especiales. Por ejemplo, el camino <math>P_n</math>
tiene <math>d(P_n) = \lfloor n/2 \rfloor</math> y el ciclo <math>C_n</math> tiene <math>d(C_n)=\lceil n/2\rceil</math>.

== Computando la dimensión bipartita ==
La tarea computacional de determinar la dimensión bipartita de un grafo dado <math>G</math> es un [[problema de optimización]] . El [[problema de decisión]] correspondiente puede ser fraseado como sigue:

: INSTANCIA: Un grafo <math>G=(V,E)</math> y un entero positivo <math>k</math>.
: PREGUNTA: El grafo <math>G</math> admite una cubierta biclique de arista que contiene como sumo <math>k</math> bicliques?

Este problema aparece como el problema '''GT18''' en el libro clásico de Garey y Johnson en [[NP-completo|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 <math>\mathcal{S}=\{S_1,\ldots,S_n\}</math> de subconjuntos de un conjunto finito <math>\mathcal{U}</math>,
una '''base de conjunto''' para  <math>\mathcal{S}</math> es otra familia de subconjuntos <math>\mathcal{B} = \{B_1,\ldots,B_\ell\}</math> de <math>\mathcal{U}</math>, tal que cada conjunto <math>S_i</math> puede ser descrito como la unión de algunos elementos de la base <math>\mathcal{B}</math>. El problema de base del conjunto consiste en lo que sigue:

: INSTANCIA: Un conjunto finito <math>\mathcal{U}</math>, una familia <math>\mathcal{S}=\{S_1,\ldots,S_n\}</math> de subconjuntos de <math>\mathcal{U}</math>, y un entero positivo ''k''.
: PREGUNTA: Existe una base de conjunto para <math>\mathcal{S}</math> de tamaño como máximo <math>k</math>?

En su formulación anterior, el problema fue probado  ser [[NP-completo]] por Orlin (1977), incluso para [[Grafo bipartito|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 <math>O(\log\,\!n)</math>, donde <math>n</math> 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 [[Algoritmo de aproximación|algoritmos de aproximación]], Simon (1990) probó que el problema no puede ser aproximado bien (suponiendo que <math>P\neq NP</math>; ver [[Clases de complejidad P y NP]]). De hecho, la dimensión bipartita es [[NP-difícil]] de aproximar en un rango <math>|V|^{1/3-\epsilon}</math> para cada <math>\epsilon>0</math> fijo, incluso para grafos bipartitos (Gruber & Holzer 2007).

En contraste, probar que el problema es [[Complejidad parametrizada|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 {{Harvtxt|Downey|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 <math>n</math> vértices, es posible decidir en tiempo <math>O(f(k))+n^3</math> con <math>f(k) = 2^{k2^{k-1}+3k}</math> si la dimensión bipartita de este grafo es como máximo <math>k</math> (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 [[Seguridad informática|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 leucocitarios humanos|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 [[Clique|cliques]] que se necesita para cubrir todas las aristas de un grafo.

* {{Obra citada|título=Proceedings of the Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, 5–7 January 1997, New Orleans, Louisiana.|apellidos=Amilhastre|nombre=Jérôme|url=http://portal.acm.org/citation.cfm?id=314175|editorial=ACM/SIAM|capítulo=Computing a minimum biclique cover is polynomial for bipartite domino-free graphs|páginas=36–42|apellidos2=Janssen|nombre2=Philippe|apellidos3=Vilarem|nombre3=Marie-Catherine|year=1997}}
* {{Obra citada|título=3rd Caribbean Conference on Combinatorics and Computing|apellidos=de Caen|nombre=Dominique|editorial=Department of Mathematics, University of the West Indies|capítulo=The Boolean rank of zero-one matrices|páginas=169–173|apellidos2=Gregory|nombre2=David A.|apellidos3=Pullman|nombre3=Norman J.|editor=Cadogan|nombre-editor=Charles C.|year=1981}}.
* {{Obra citada|título=Parameterized complexity|apellidos=Downey|nombre=Rod|enlaceautor=Rod Downey|editorial=Springer|apellidos2=Fellows|nombre2=Michael R.|enlaceautor2=Michael Fellows|ISBN=0-387-94883-X|year=1999}}.
* {{Obra citada|título=13th ACM Symposium on Access Control Models and Technologies (SACMAT 2008)|apellidos=Ene|nombre=Alina|editorial=ACM|capítulo=Fast exact and heuristic methods for role minimization problems|páginas=1–10|apellidos2=Horne|nombre2=William G.|apellidos3=Milosavljevic|nombre3=Nikola|apellidos4=Rao|nombre4=Prasad|apellidos5=Schreiber|nombre5=Robert|apellidos6=Tarjan|nombre6=Robert Endre|enlaceautor6=Robert Tarjan|editor=Ray|nombre-editor=Indrakshi|editor2=Li|year=2008|editor2-first=Ninghui}}.
* {{Obra citada|título=Bipartite dimensions and bipartite degrees of graphs|apellidos=Fishburn|nombre=Peter C.|enlaceautor=Peter C. Fishburn|pub-periódica=[[Discrete Mathematics (journal)|Discrete Mathematics]]|número=1–3|volumen=160|páginas=127–148|apellidos2=Hammer|nombre2=Peter Ladislaw|enlaceautor2=Peter Ladislaw Hammer|DOI=10.1016/0012-365X(95)00154-O|year=1996}}.
* {{Obra citada|título=Covering graphs with few complete bipartite subgraphs|apellidos=Fleischner|nombre=Herbert|pub-periódica=[[Theoretical Computer Science (journal)|Theoretical Computer Science]]|número=21–23|volumen=410|páginas=2045–2053|apellidos2=Mujuni|nombre2=Egbert|apellidos3=Paulusma|nombre3=Daniël|apellidos4=Szeider|nombre4=Stefan|DOI=10.1016/j.tcs.2008.12.059|year=2009}}.
* {{Obra citada|título=Computers and Intractability: A Guide to the Theory of NP-Completeness|apellidos=Garey|nombre=Michael R.|enlaceautor=Michael Garey|editorial=W.H. Freeman|apellidos2=Johnson|nombre2=David S.|enlaceautor2=David S. Johnson|ISBN=0-7167-1045-5|year=1979}}.
* {{Obra citada|título=Efficient data storage in large nanoarrays|apellidos=Gottlieb|nombre=Lee-Ad J.|pub-periódica=Theory of Computing Systems|número=4|volumen=38|páginas=503–536|apellidos2=Savage|nombre2=John E.|apellidos3=Yerukhimovich|nombre3=Arkady|enlaceautor2=John E. Savage|DOI=10.1007/s00224-004-1196-9|year=2005}}.
* {{Obra citada|título=11th International Conference on Developments in Language Theory (DLT 2007)|apellidos=Gruber|nombre=Hermann|editorial=Springer|lugar=Turku, Finland|capítulo=Inapproximability of Nondeterministic State and Transition Complexity Assuming P <> NP.|serie=LNCS|volumen=4588|páginas=205–216|apellidos2=Holzer|nombre2=Markus|editor=Harju|nombre-editor=Terjo|editor2=Karhumäki|editor3=Lepistö|DOI=10.1007/978-3-540-73208-2_21|year=2007|editor2-first=Juhani}}.
* {{Obra citada|título=The Biclique Covering Number of Grids|apellidos=Guo|nombre=Krystal|pub-periódica=The Electronic Journal of Combinatorics|número=4|volumen=26|apellidos2=Huynh|nombre2=Tony|apellidos3=Macchia|nombre3=Marco|DOI=10.37236/8316|year=2019}}.
* {{Obra citada|título=A survey of clique and biclique coverings and factorizations of (0,1)-matrices|apellidos=Monson|nombre=Sylvia D.|pub-periódica=Bulletin of the ICA|volumen=14|páginas=17–86|apellidos2=Pullman|nombre2=Norman J.|apellidos3=Rees|nombre3=Rolf|year=1995}}.
* {{Obra citada|título=A mathematical analysis of human leukocyte antigen serology|apellidos=Nau|nombre=D. S.|url=http://www.cs.umd.edu/~nau/papers/nau1978mathematical.pdf|pub-periódica=Mathematical Biosciences|número=3–4|volumen=40|páginas=243–270|apellidos2=Markowsky|nombre2=G.|apellidos3=Woodbury|nombre3=M. A.|apellidos4=Amos|nombre4=D. B.|DOI=10.1016/0025-5564(78)90088-3|year=1978}}.
* {{Obra citada|título=Combinatorial Pattern Matching|apellidos=Nor|nombre=Igor|capítulo=Mod/Resc Parsimony Inference|serie=Lecture Notes in Computer Science|volumen=6129|páginas=202–213|apellidos2=Hermelin|nombre2=Danny|apellidos3=Charlat|nombre3=Sylvain|apellidos4=Engelstadter|nombre4=Jan|apellidos5=Reuter|nombre5=Max|apellidos6=Duron|nombre6=Olivier|apellidos7=Sagot|nombre7=Marie-France|ISBN=978-3-642-13508-8|DOI=10.1007/978-3-642-13509-5_19|year=2010}}
* {{Obra citada|título=Contentment in graph theory: covering graphs with cliques|apellidos=Orlin|nombre=James|enlaceautor=James B. Orlin|pub-periódica=[[Indagationes Mathematicae]]|número=5|volumen=80|páginas=406–424|DOI=10.1016/1385-7258(77)90055-5|year=1977}}.
* {{Obra citada|título=20th International Parallel and Distributed Processing Symposium (IPDPS 2006)|apellidos=Shu|nombre=Guoqiang|editorial=IEEE|capítulo=A note on broadcast encryption key management with applications to large scale emergency alert systems.|apellidos2=Lee|nombre2=David|apellidos3=Yannakakis|nombre3=Mihalis|year=2006}}.
* {{Obra citada|título=On Approximate Solutions for Combinatorial Optimization Problems|apellidos=Simon|nombre=Hans-Ulrich|pub-periódica=[[SIAM Journal on Discrete Mathematics]]|número=2|volumen=3|páginas=294–310|DOI=10.1137/0403025|year=1990}}.
* {{Obra citada|título=The set basis problem is NP-complete|apellidos=Stockmeyer|nombre=Larry J.|enlaceautor=Larry J. Stockmeyer|editorial=IBM|serie=Technical Report RC-5431|year=1975}}.

== Enlaces externos ==

* [https://11011110.github.io/blog/2008/03/31/biclique-covers.html Entrada de blog sobre dimensión bipartita] por [[David Eppstein]]
[[Categoría:Problemas NP-completos]]
[[Categoría:Teoría de grafos]]
[[Categoría:Invariantes de grafos]]