Corte de gráfico máximo

El corte máximo de un gráfico es un corte cuyo tamaño no es menor que el tamaño de cualquier otro corte. El problema de determinar el corte máximo de un gráfico se conoce como problema de corte máximo .

El problema se puede formular de la siguiente manera. Se debe encontrar un subconjunto de vértices S tal que el número de aristas entre S y su complemento sea el mayor posible.

Hay una versión extendida, el problema de corte máximo ponderado . En esta versión, a cada arista se le asigna un número real, su peso es , y el objetivo no es maximizar el número de aristas, sino el peso total de la arista entre S y su complemento. El problema de corte máximo ponderado a menudo, pero no siempre, se limita a pesos no negativos porque los pesos negativos pueden cambiar la naturaleza del problema.

Complejidad computacional

El siguiente problema de resolubilidad , relacionado con el corte máximo, ha sido ampliamente estudiado en informática teórica :

Dado un gráfico G y un entero k , determine si hay un corte en G que sea al menos k .

Se sabe que este problema es NP-completo . La NP-completitud de un problema se puede mostrar, por ejemplo, reduciendo del problema de satisfacibilidad máxima 2 ( problema de satisfacibilidad máxima con restricciones) [1] . Una versión ponderada del problema de solucionabilidad está incluida en los 21 problemas de Karp NP-completos [2] . Karp mostró la completitud de NP mediante la reducción del problema de partición .

La variante de optimización canónica del problema de resolución anterior se conoce como el " problema de corte máximo " y se define de la siguiente manera:

Sea dada la gráfica G , es necesario encontrar el corte máximo.

Algoritmos de tiempo polinomial

Dado que el problema de corte máximo es NP-duro, no existen algoritmos de tiempo polinomial para el problema de corte máximo para gráficos generales.

Sin embargo, para grafos planos , el problema de corte máximo es dual al problema del cartero chino (el problema de encontrar el camino más corto que rodee todos los bordes al menos una vez), en el sentido de que los bordes que no pertenecen al máximo corte de G son duales a los bordes, que se recorren muchas veces en el recorrido óptimo del gráfico dual para el gráfico G. La caminata óptima forma una curva que se interseca a sí misma y divide el plano en dos subconjuntos, un subconjunto de puntos para los cuales el orden con respecto a la curva es par y un subconjunto de puntos para los cuales el orden es impar. Estos dos subconjuntos forman un corte que incluye todos los bordes que son duales a los bordes que aparecen un número impar de veces en el recorrido. El problema del cartero chino puede resolverse en tiempo polinomial, y esta dualidad permite resolver el problema del corte máximo para grafos planos en tiempo polinomial [3] . Se sabe, sin embargo, que el problema de bisección máxima es NP-duro [4] .

Algoritmos de aproximación

El problema de corte máximo es APX-duro (Papadimitrou y Yannakakis probaron MaxSNP-completo para este problema [5] ), lo que significa que no existe un esquema de aproximación de tiempo polinomial (PTAS) arbitrariamente cercano a la solución óptima, a menos que P = NP. Por lo tanto, cualquier algoritmo de aproximación de tiempo polinomial da un coeficiente de aproximación estrictamente menor que uno.

Hay un algoritmo simple de aproximación probabilística de 0.5 - para cualquier vértice, lanzamos una moneda para decidir a qué parte del corte atribuir este vértice [6] [7] . Se espera que la mitad de los bordes se corten. Este algoritmo se puede desaleatorizar utilizando el método de probabilidades condicionales . Por lo tanto, existe un algoritmo de tiempo polinomial determinista simple con una aproximación de 0,5 [8] [9] . Uno de estos algoritmos comienza con una partición arbitraria de los vértices de un gráfico dado y mueve un vértice en un paso de una parte del corte a otra, mejorando la solución en cada paso siempre que sea posible. El número de iteraciones del algoritmo no excede , ya que el algoritmo mejora el corte en al menos un borde. Cuando el algoritmo se detiene, al menos la mitad de las aristas que inciden en cualquier vértice pertenecen al corte; de ​​lo contrario, mover el vértice mejoraría el corte (aumentaría el tamaño del corte). Así, el corte incluye al menos bordes.

El algoritmo de aproximación en tiempo polinomial para el problema de corte máximo con el coeficiente de aproximación más conocido es el método de Gemans y Williamson que utiliza programación semidefinida y redondeo probabilístico . El método da un coeficiente de aproximación , donde [10] [11] . Si la hipótesis del juego único es cierta, este es el mejor factor de aproximación posible para el corte máximo [12] . Salvo tales supuestos no probados, se ha demostrado que es NP-difícil aproximar el valor del corte máximo con un factor mejor que [13] [14] .

Véase también

Notas

  1. ↑ Garey, Johnson, 1979 .
  2. ↑ Karpa, 1972 .
  3. ↑ Hadlock, 1975 .
  4. ↑ Jansen, Karpinski, Lingas, Seidel, 2005 .
  5. ↑ Papadimitriou y Yannakakis, 1991 .
  6. ↑ Mitzenmacher, Upfal, 2005 , pág. Secta. 6.2.
  7. ↑ Motwani, Raghavan, 1995 , pág. Secta. 5.1.
  8. ↑ Mitzenmacher, Upfal, 2005 , pág. Secta. 6.3..
  9. ↑ Khuller, Raghavachari, Young, 2007 .
  10. ↑ Gaur, Krishnamurti, 2007 .
  11. ↑ Ausiello, Crescenzi et al., 2003 .
  12. ↑ Khot, Kindler, Mossel, O'Donnell, 2007 .
  13. ↑ Håstad, 2001 .
  14. ↑ Trevisan, Sorkin, Sudán, Williamson, 2000 .

Literatura

El problema de corte máximo (versión optimizada) es el problema ND14 del Apéndice B (pág. 399). El problema de corte máximo (problema de solucionabilidad) es el problema ND16 del Apéndice A2.2. El subgrafo bipartito máximo (problema de resolubilidad) es el problema GT25 del Apéndice A1.2.

Lecturas adicionales

Enlaces