LISTA DE PROBLEMAS

En los campos matemáticos de la teoría de grafos y optimización combinatoria , la dimensión bipartito o número cubierta biclique de un gráfico G  = ( V ,  E ) es el número mínimo de bicliques (es decir subgraphs bipartitos completos), necesaria para cubrir todos los bordes en E . Una colección de bicliques que cubre todos los bordes en G se llama cubierta de borde biclique , o a veces cubierta biclique . La dimensión bipartita de G a menudo se denota con el símbolo d ( G).

Ejemplo [ editar ]

Un ejemplo para una cubierta de borde biclique se da en los siguientes diagramas:

• Ejemplo para cubierta de borde biclique
• 

  Un gráfico bipartito ...
 
• 

  ... y una cubierta con cuatro bicliques
 
• 

  el biclique rojo de la tapa
 
• 

  el biclique azul de la tapa
 
• 

  el biclique verde de la tapa
 
• 

  el biclique negro de la tapa

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

La dimensión biclique del gráfico completo n- vértice ,$${\ displaystyle K_ {n}} es $${\ displaystyle \ lceil \ log _ {2} n \ rceil}.

La dimensión bipartita de un gráfico de corona de vértice 2n es igual a$${\ displaystyle \ sigma (n)}, dónde

$${\ 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 ). Fishburn & Hammer (1996) determinan la dimensión bipartita para algunos gráficos especiales. Por ejemplo, el camino$${\ displaystyle P_ {n}} tiene $${\ displaystyle d (P_ {n}) = \ lfloor n / 2 \ rfloor} y el ciclo $${\ displaystyle C_ {n}} tiene $${\ displaystyle d (C_ {n}) = \ lceil n / 2 \ rceil}.

Calcular la dimensión bipartita [ editar ]

La tarea computacional de determinar la dimensión bipartita para un gráfico G dado es un problema de optimización . El problema de decisión para la dimensión bipartita se puede expresar como:

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

PREGUNTA: ¿G admite una cubierta de borde biclique que contiene como máximo $${\ displaystyle k} bicliques?

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

El problema de la base establecida aparece como el problema SP7 en el libro de Garey y Johnson. Aquí para una familia$${\ displaystyle {\ mathcal {S}} = \ {S_ {1}, \ ldots, S_ {n} \}} de subconjuntos de un conjunto finito $${\ displaystyle {\ mathcal {U}}}, una base establecida para$${\ displaystyle {\ mathcal {S}}} es otra familia de subconjuntos $${\ displaystyle {\ mathcal {B}} = \ {B_ {1}, \ ldots, B _ {\ ell} \}} de $${\ displaystyle {\ mathcal {U}}}, de modo que cada conjunto $${\ displaystyle S_ {i}} puede describirse como la unión de algunos elementos básicos de $${\ displaystyle {\ mathcal {B}}}. El problema de la base establecida ahora se da de la siguiente manera:

INSTANCIA: un conjunto finito $${\ displaystyle {\ mathcal {U}}}, una familia $${\ displaystyle {\ mathcal {S}} = \ {S_ {1}, \ ldots, S_ {n} \}} de subconjuntos de $${\ displaystyle {\ mathcal {U}}}, y un entero positivo k .

PREGUNTA: ¿Existe una base establecida de tamaño como máximo? $${\ displaystyle k} para $${\ displaystyle {\ mathcal {S}}}?

En su antigua formulación, el problema fue demostrado ser NP -Complete por Orlin (1977) , incluso para gráficos bipartitos . Stockmeyer (1975) demostró que la formulación como problema de base establecida era NP completa antes . El problema sigue siendo NP- duro incluso si restringimos nuestra atención a los gráficos bipartitos cuya dimensión bipartita se garantiza como máximo$${\ displaystyle O (\ log \, \! n)}, con n indicando el tamaño de la instancia del problema dada ( Gottlieb, Savage & Yerukhimovich 2005 ). En el lado positivo, el problema se puede resolver en tiempo polinómico en gráficos bipartitos libres de dominó ( Amilhastre, Janssen y Vilarem 1997 ).

Con respecto a la existencia de algoritmos de aproximación , Simon (1990) demostró que el problema no se puede aproximar bien (suponiendo P  ≠  NP ). De hecho, la dimensión bipartita es NP- difícil de aproximar dentro de$${\ displaystyle | V | ^ {1 / 3- \ epsilon}} por cada fijo {\ displaystyle \ epsilon> 0}, ya para gráficos bipartitos ( Gruber y Holzer 2007 ).

En contraste, probar 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 y col. (2009) también proporcionan un límite concreto sobre el tamaño del grano resultante, que mientras tanto Nor et al. (2010) . De hecho, para un gráfico bipartito dado en n vértices, se puede decidir a tiempo$${\ displaystyle O (f (k)) + n ^ {3}} con $${\ displaystyle f (k) = 2 ^ {k2 ^ {k-1} + 3k}}si su dimensión bipartita es como máximo k ( Nor et al. 2010 )

Aplicaciones [ editar ]

El problema de determinar la dimensión bipartita de un gráfico aparece en varios contextos de computación. Por ejemplo, en los sistemas informáticos, a los diferentes usuarios de un sistema se les puede permitir o no acceder 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 tener 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 varios usuarios. El problema de la minería de roleses encontrar un conjunto mínimo de roles, de modo que para cada usuario, sus roles 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 gráfico bipartito, cuyos bordes son permisos. Cada biclique en este gráfico es una función potencial, y las soluciones óptimas para el problema de la minería de funciones son precisamente las cubiertas mínimas de los bordes biclique ( 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 tiene que encriptarse usando alguna 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 óptimo de generación de claves es encontrar un conjunto mínimo de claves de cifrado para garantizar una transmisión segura. Como se indicó anteriormente, el problema se puede modelar utilizando un gráfico bipartito cuyas cubiertas de borde biclique mínimas coinciden con las soluciones para el problema óptimo de generación de claves ( Shu, Lee y Yannakakis 2006 ).

Una aplicación diferente radica en la biología, donde se usan cubiertas mínimas de borde biclique en modelos matemáticos de serología de antígeno leucocitario humano (HLA) ( Nau et al. 1978 ).

El árbol de expansión mínimo capacitado es un árbol de expansión de costo mínimo de un gráfico que tiene un nodo raíz designado$${\ displaystyle r} y satisface la restricción de capacidad $${\ displaystyle c}. La restricción de capacidad asegura que todos los subárboles (subgráficos máximos conectados a la raíz por un solo borde) inciden en el nodo raíz$${\ displaystyle r} no tiene más que $${\ displaystyle c}nodos Si los nodos del árbol tienen pesos, entonces la restricción de capacidad puede interpretarse de la siguiente manera: la suma de los pesos en cualquier subárbol no debe ser mayor que$${\ displaystyle c}. Los bordes que conectan los subgrafos al nodo raíz se llaman puertas . Encontrar la solución óptima es NP-hard.

Algoritmos [ editar ]

Supongamos que tenemos un gráfico $${\ displaystyle G = (V, E)}, $${\ displaystyle n = | G |} con una raíz $${\ displaystyle r \ en G}. Dejar$${\ displaystyle a_ {i}} ser todos los demás nodos en $${\ displaystyle G}. Dejar$${\ displaystyle c_ {ij}}ser el costo límite entre ver $${\ displaystyle a_ {i}} y $${\ displaystyle a_ {j}} que forman una matriz de costos $${\ displaystyle C = {c_ {ij}}}.

Esaú-Williams heurística ^[2] [ editar ]

La heurística de Esau-Williams encuentra CMST subóptimos que están muy cerca de las soluciones exactas, pero en promedio EW produce mejores resultados que muchas otras heurísticas.

Inicialmente, todos los nodos están conectados a la raíz $${\ displaystyle r} (gráfico de estrella) y el costo de la red es $${\ displaystyle \ displaystyle \ sum _ {i = 0} ^ {n} c_ {ri}}; Cada uno de estos bordes es una puerta. En cada iteración, buscamos al vecino más cercano$${\ displaystyle a_ {j}} para cada nodo en $${\ displaystyle G- {r}} y evaluar la función de compensación: $${\ displaystyle t (a_ {i}) = g_ {i} -c_ {ij}}. Buscamos lo mejor$${\ displaystyle t (a_ {i})} entre las compensaciones positivas y, si el subárbol resultante no viola las restricciones de capacidad, elimine la puerta $${\ displaystyle g_ {i}} conectando el $${\ displaystyle i}-th subárbol a $${\ displaystyle a_ {j}} por un borde $${\ displaystyle c_ {ij}}. Repetimos las iteraciones hasta que no podamos realizar más mejoras en el árbol.

Heurística de Esau-Williams para calcular un CMST subóptimo:

función CMST ( c , C , r ):
     T = {$${\ displaystyle c_ {1r}}
  
, $${\ displaystyle c_ {2r}}
  
, ..., $${\ displaystyle c_ {nr}}
  
}
     mientras tiene cambios:
         para cada nodo$${\ displaystyle a_ {i}}
  

            $${\ displaystyle a_ {j}}
  
 = nodo más cercano en un subárbol diferente
            $${\ displaystyle t (a_ {i})}
  
 = $${\ displaystyle g_ {i}}
  
 - $${\ displaystyle c_ {ij}}
  

        t_max = max ($${\ displaystyle t (a_ {i})}
  
)
         k = i tal que$${\ displaystyle t (a_ {i})}
  
= t_max
         if ( costo (i) + costo (j) <= c )
             T = T -$${\ displaystyle g_ {k}}
  

            T = unión T$${\ displaystyle c_ {kj}}
  

    volver  T

Es fácil ver que EW encuentra una solución en tiempo polinomial.

La heurística de Sharma [ editar ]

Sharma es heurística. ^[3]

Aplicaciones [ editar ]

El problema de CMST es importante en el diseño de la red: cuando muchas computadoras terminales tienen que estar conectadas al concentrador central, la configuración en estrella generalmente no es el diseño de costo mínimo. Encontrar un CMST que organice los terminales en subredes puede reducir el costo de implementar una red.

problema del cartero chino , el recorrido por el cartero o el problema de inspección de ruta es encontrar una ruta o circuito cerrado más corto que visite cada borde de un gráfico no conectado (conectado) . Cuando el gráfico tiene un circuito euleriano (una caminata cerrada que cubre cada borde una vez), ese circuito es una solución óptima. De lo contrario, el problema de optimización es encontrar el número más pequeño de bordes de gráfico para duplicar (o el subconjunto de bordes con el peso total mínimo posible) de modo que el multigrafo resultante tenga un circuito euleriano. ^[1]Se puede resolver en tiempo polinómico . ^[2]

El problema fue estudiado originalmente por el matemático chino Kwan Mei-Ko en 1960, cuyo artículo chino fue traducido al inglés en 1962. ^[3] El nombre original "problema del cartero chino" fue acuñado en su honor; diferentes fuentes atribuyen las monedas a Alan J. Goldman o Jack Edmonds , quienes estaban en la Oficina Nacional de Normas de los EE. UU. en ese momento. ^[4] [5]

Una generalización es elegir cualquier conjunto T de manera uniforme muchos vértices que se van a unir por un conjunto de aristas en el gráfico cuya impar grados vértices son precisamente los de T . Tal conjunto se llama T- join. Este problema, el problema de unión T , también se puede resolver en tiempo polinómico mediante el mismo enfoque que resuelve el problema del cartero.

Solución no dirigida y T- une [ editar ]

El problema de la inspección de ruta no dirigida se puede resolver en tiempo polinómico mediante un algoritmo basado en el concepto de unión en T. Deje que T sea ​​un subconjunto del conjunto de vértices de un gráfico. Un conjunto de aristas J se denomina T -join si la colección de vértices que tienen un número impar de aristas incidentes en J es exactamente el conjunto T . A T existe -join siempre que cada componente conectado de la gráfica contiene un número par de vértices en T . El problema de T- Join es encontrar una T-unirse con el número mínimo posible de bordes o el peso total mínimo posible.

Para cualquier T , una unión T más pequeña (cuando existe) necesariamente consiste en$${\ displaystyle {\ tfrac {1} {2}} | T |}caminos que unen los vértices de T en pares. Los caminos serán tales que la longitud total o el peso total de todos ellos sea lo más pequeño posible. En una solución óptima, no hay dos de estos caminos que compartan ningún borde, pero pueden tener vértices compartidos. Se puede obtener una unión T mínima construyendo un gráfico completo en los vértices de T , con bordes que representen los caminos más cortos en el gráfico de entrada dado, y luego encontrando una coincidencia perfecta de peso mínimo en este gráfico completo. Los bordes de esta coincidencia representan caminos en el gráfico original, cuya unión forma la unión T deseada. Tanto la construcción del gráfico completo como la búsqueda de una coincidencia se pueden hacer en O ( n³ ) pasos computacionales.

Para el problema de inspección de ruta, T debe elegirse como el conjunto de todos los vértices de grados impares. Por los supuestos del problema, todo el gráfico está conectado (de lo contrario, no existe un recorrido), y por el lema de apretón de manos tiene un número par de vértices impares, por lo que siempre existe una unión en T. Duplicar los bordes de una unión T hace que el gráfico dado se convierta en un multigrafo euleriano (un gráfico conectado en el que cada vértice tiene un grado par), de lo que se deduce que tiene un recorrido Euler , un recorrido que visita cada borde del multigrafo Exactamente una vez. Este recorrido será una solución óptima al problema de inspección de ruta. ^[6] [2]

Solución dirigida [ editar ]

En un gráfico dirigido, se aplican las mismas ideas generales, pero se deben utilizar diferentes técnicas. Si el gráfico dirigido es Euleriano, solo se necesita encontrar un ciclo de Euler. Si no es así, uno debe encontrar las uniones T , que en este caso implica encontrar caminos desde vértices con un grado mayor que su grado de salida hasta aquellos con un grado mayor que su grado de entrada de tal manera que en grado de cada vértice igual a su grado de salida. Esto puede resolverse como una instancia del problema de flujo de costo mínimo en el que hay una unidad de suministro por cada unidad de exceso de grado y una unidad de demanda por cada unidad de exceso de grado. Como tal, se puede resolver en O (| VEl | ² | E |) tiempo. Existe una solución si y solo si el gráfico dado está fuertemente conectado . ^[2] [7]

Problema del cartero ventoso [ editar ]

El problema del cartero ventoso es una variante del problema de inspección de ruta en el que la entrada es un gráfico no dirigido, pero donde cada borde puede tener un costo diferente para atravesarlo en una dirección que para atravesarlo en la otra dirección. En contraste con las soluciones para gráficos dirigidos y no dirigidos, es NP-completo . ^[8] [9]

Aplicaciones [ editar ]

Varios problemas combinatorios se han reducido al problema del cartero chino, incluida la búsqueda de un corte máximo en un gráfico plano y un circuito de longitud media mínima en un gráfico no dirigido. ^[10]

Variantes [ editar ]

Se han estudiado algunas variantes del problema del cartero chino y se ha demostrado que son NP completas . ^[11]

• El problema del cartero chino para gráficos mixtos: para este problema, algunos de los bordes se pueden dirigir y, por lo tanto, solo se pueden visitar desde una dirección. Cuando el problema requiere un recorrido mínimo de un dígrafo (o multidigraph) se le conoce como el "problema del barrendero de la calle de Nueva York". ^[12]
• El problema del cartero k- chino: encuentre k ciclos, todos comenzando en una ubicación designada, de modo que cada borde se atraviese al menos un ciclo. El objetivo es minimizar el costo del ciclo más costoso.
• El "problema del cartero rural": resuelva el problema con algunos bordes no necesarios.