Para un gráfico , un corte máximo es un corte cuyo tamaño es al menos el tamaño de cualquier otro corte. Es decir, es una partición de los vértices del gráfico en dos conjuntos complementarios S y T , de manera que el número de aristas entre el conjunto S y el conjunto T sea lo más grande posible. El problema de encontrar un corte máximo en una gráfica se conoce como Problema de corte máximo.
El problema se puede plantear simplemente de la siguiente manera. Se quiere un subconjunto S del conjunto de vértices de modo que el número de aristas entre S y el subconjunto complementario sea lo más grande posible. De manera equivalente, se desea un subgrafo bipartito del gráfico con tantos bordes como sea posible.
Existe una versión más general del problema llamada Max-Cut ponderado, donde cada borde está asociado con un número real, su peso , y el objetivo es maximizar el peso total de los bordes entre S y su complemento en lugar del número de aristas. Los bordes. El problema de corte máximo ponderado que permite ponderaciones tanto positivas como negativas se puede transformar trivialmente en un problema de corte mínimo ponderado cambiando el signo en todos los pesos.
Complejidad computacional
El siguiente problema de decisión relacionado con los cortes máximos se ha estudiado ampliamente en la informática teórica :
- Dada una gráfica G y un número entero k , determinar si hay un corte de tamaño al menos k en G .
Se sabe que este problema es NP-completo . Es fácil ver que el problema está en NP : una respuesta afirmativa es fácil de probar presentando un corte lo suficientemente grande. La NP-completitud del problema se puede mostrar, por ejemplo, mediante una reducción de la máxima 2-satisfacibilidad (una restricción del problema de máxima satisfacibilidad ). [1] La versión ponderada del problema de decisión fue uno de los 21 problemas NP-completos de Karp ; [2] Karp mostró el NP-completo mediante una reducción del problema de la partición .
La canónica variante de optimización del problema de decisión anterior se conoce generalmente como el -Cut Máximo Problema o Max-Cut y se define como:
- Dado un gráfico G , encuentre un corte máximo.
Se sabe que la variante de optimización es NP-Hard. Se sabe que el problema opuesto, el de encontrar un corte mínimo, se puede resolver de manera eficiente mediante el algoritmo de Ford-Fulkerson .
Algoritmos
Algoritmos de tiempo polinomial
Como el problema de Max-Cut es NP-hard , no se conocen algoritmos de tiempo polinómico para Max-Cut en gráficos generales.
Gráficos planos
Sin embargo, en gráficos planos , el problema de corte máximo es dual con el problema de inspección de ruta (el problema de encontrar un recorrido más corto que visite cada borde de un gráfico al menos una vez), en el sentido de que los bordes que no pertenecen a un máximo de corte de un conjunto de un gráfico G son los duales de los bordes que están duplicando en un viaje de inspección óptima de la dual gráfico de G . El recorrido de inspección óptimo forma una curva que se interseca automáticamente y separa el plano en dos subconjuntos, el subconjunto de puntos para los que el número de devanado de la curva es par y el subconjunto para el que el número de devanados es impar; estos dos subconjuntos forman un corte que incluye todos los bordes cuyos duales aparecen un número impar de veces en el recorrido. El problema de inspección de ruta puede resolverse en tiempo polinomial, y esta dualidad permite que el problema de corte máximo también se resuelva en tiempo polinomial para gráficas planas. [3] Sin embargo, se sabe que el problema de la bisección máxima es NP-duro. [4]
Algoritmos de aproximación
El problema de corte máximo es APX-difícil , [5] lo que significa que no existe un esquema de aproximación de tiempo polinómico (PTAS), arbitrariamente cercano a la solución óptima, para él, a menos que P = NP. Por lo tanto, todo algoritmo de aproximación de tiempo polinómico conocido logra una relación de aproximación estrictamente menor que uno.
Existe un algoritmo de aproximación 0.5 aleatorio simple : para cada vértice, lanza una moneda para decidir a qué mitad de la partición asignarla. [6] [7] Como se esperaba, la mitad de los bordes son bordes cortados. Este algoritmo puede desaleatorizarse con el método de probabilidades condicionales ; por lo tanto, también existe un algoritmo de aproximación 0.5 en tiempo polinómico determinista simple. [8] [9] Uno de estos algoritmos comienza con una partición arbitraria de los vértices del gráfico dado.y mueve repetidamente un vértice a la vez de un lado del tabique al otro, mejorando la solución en cada paso, hasta que no se puedan realizar más mejoras de este tipo. El número de iteraciones es como máximoporque el algoritmo mejora el corte en al menos un borde en cada paso. Cuando el algoritmo termina, al menos la mitad de los bordes incidentes a cada vértice pertenecen al corte, ya que de lo contrario mover el vértice mejoraría el corte. Por tanto, el corte incluye al menos bordes.
El algoritmo de aproximación de tiempo polinomial para Max-Cut con la relación de aproximación más conocida es un método de Goemans y Williamson que utiliza programación semidefinida y redondeo aleatorio que logra una relación de aproximación dónde
Si la conjetura de los juegos únicos es cierta, esta es la mejor relación de aproximación posible para un corte máximo. [12] Sin tales suposiciones no probadas, se ha demostrado que es NP-difícil aproximar el valor de corte máximo con una relación de aproximación mejor que. [13] [14]
En [15] hay un análisis extendido de 10 heurísticas para este problema, incluida la implementación de código abierto.
Aplicaciones
Física teórica
En física estadística y sistemas desordenados , el problema de Max Cut es equivalente a minimizar el hamiltoniano de un modelo de vidrio giratorio , más simplemente el modelo de Ising . [16] Para el modelo de Ising en un gráfico G y solo las interacciones del vecino más cercano, el hamiltoniano es
Aquí, cada vértice i del gráfico es un sitio de giro que puede tomar un valor de giro Una configuración de giro particiones en dos conjuntos, aquellos con giro y aquellos con giro hacia abajo Denotamos con el conjunto de bordes que conectan los dos conjuntos. Entonces podemos reescribir el hamiltoniano como
Minimizar esta energía es equivalente al problema de corte mínimo o al establecer los pesos del gráfico como el problema del corte máximo. [dieciséis]
Diseño de circuito
El problema de corte máximo tiene aplicaciones en el diseño VLSI . [dieciséis]
Ver también
- Corte mínimo
- K-corte mínimo
- Ciclo impar transversal , equivalente a pedir el subgrafo inducido bipartito más grande
Notas
- ^ Garey y Johnson (1979) .
- ^ Karp (1972) .
- ^ Hadlock (1975) .
- ^ Jansen y col. (2005) .
- ^ Papadimitriou y Yannakakis (1991) prueban la completitud de MaxSNP .
- ^ Mitzenmacher y Upfal (2005) , secc. 6.2.
- ^ Motwani y Raghavan (1995) , secc. 5.1.
- ^ Mitzenmacher y Upfal (2005) , secc. 6.3.
- ^ Khuller, Raghavachari y Young (2007) .
- ^ Gaur y Krishnamurti (2007) .
- ^ Ausiello y col. (2003)
- ^ Khot y col. (2007) .
- ↑ Håstad (2001)
- ^ Trevisan y col. (2000)
- ^ Dunning, Gupta y Silberholz (2018)
- ^ a b c Barahona, Francisco; Grötschel, Martin; Jünger, Michael; Reinelt, Gerhard (1988). "Una aplicación de optimización combinatoria a la física estadística y al diseño de circuitos". Investigación operativa . 36 (3): 493–513. doi : 10.1287 / opre.36.3.493 . ISSN 0030-364X . JSTOR 170992 .
Referencias
- Ausiello, Giorgio; Crescenzi, Pierluigi; Gambosi, Giorgio; Kann, Viggo; Marchetti-Spaccamela, Alberto; Protasi, Marco (2003), Complejidad y aproximación: problemas de optimización combinatoria y sus propiedades de aproximación , Springer.
- El corte máximo (versión de optimización) es el problema ND14 en el Apéndice B (página 399).
- Garey, Michael R .; Johnson, David S. (1979), Computadoras e intratabilidad: una guía para la teoría de NP-Completeness , WH Freeman, ISBN 978-0-7167-1045-5.
- El corte máximo (versión de decisión) es el problema ND16 en el Apéndice A2.2.
- El subgrafo bipartito máximo (versión de decisión) es el problema GT25 en el Apéndice A1.2.
- Gaur, Daya Ram; Krishnamurti, Ramesh (2007), "LP redondeo y extensiones", en González, Teófilo F. (ed.), Manual de algoritmos de aproximación y metaheurística , Chapman & Hall / CRC.
- Goemans, Michel X .; Williamson, David P. (1995), "Algoritmos de aproximación mejorados para problemas de corte máximo y satisfacibilidad mediante programación semidefinida", Journal of the ACM , 42 (6): 1115-1145, doi : 10.1145 / 227683.227684 , S2CID 15794408.
- Hadlock, F. (1975), "Encontrar un corte máximo de un gráfico plano en tiempo polinomial", SIAM J. Comput. , 4 (3): 221–225, doi : 10.1137 / 0204019.
- Håstad, Johan (2001), "Algunos resultados óptimos de inaproximabilidad", Journal of the ACM , 48 (4): 798–859, doi : 10.1145 / 502090.502098 , S2CID 5120748.
- Jansen, Klaus; Karpinski, Marek ; Lingas, Andrzej; Seidel, Eike (2005), "Polynomial Time Approximation Schemes for MAX-BISECTION on Planar and Geometric Graphs", SIAM Journal on Computing , 35 (1): 110-119, CiteSeerX 10.1.1.62.5082 , doi : 10.1137 / s009753970139567x.
- Karp, Richard M. (1972), " Reducibilidad entre problemas combinatorios ", en Miller, RE; Thacher, JW (eds.), Complexity of Computer Computation , Plenum Press, págs. 85-103.
- Khot, Subhash ; Kindler, Guy; Mossel, Elchanan; O'Donnell, Ryan (2007), "¿Resultados óptimos de inaproximación para MAX-CUT y otros CSP de 2 variables?" , SIAM Journal on Computing , 37 (1): 319–357, doi : 10.1137 / S0097539705447372.
- Khuller, Samir; Raghavachari, Balaji; Young, Neal E. (2007), "Métodos codiciosos", en González, Teófilo F. (ed.), Manual de algoritmos de aproximación y metaheurística , Chapman & Hall / CRC.
- Mitzenmacher, Michael ; Upfal, Eli (2005), probabilidad y computación: algoritmos aleatorios y análisis probabilístico , Cambridge.
- Motwani, Rajeev ; Raghavan, Prabhakar (1995), algoritmos aleatorios , Cambridge.
- Newman, Alantha (2008), "Max cut", en Kao, Ming-Yang (ed.), Encyclopedia of Algorithms , Springer, págs. 489–492, doi : 10.1007 / 978-0-387-30162-4_219 , ISBN 978-0-387-30770-1.
- Papadimitriou, Christos H .; Yannakakis, Mihalis (1991), "Optimización, aproximación y clases de complejidad", Journal of Computer and System Sciences , 43 (3): 425–440, doi : 10.1016 / 0022-0000 (91) 90023-X.
- Trevisan, Luca ; Sorkin, Gregory; Sudán, Madhu; Williamson, David (2000), "Gadgets, Approximation, and Linear Programming", Actas del 37º Simposio IEEE sobre Fundamentos de las Ciencias de la Computación : 617–626.
- Dunning, Iain ; Gupta, Swati; Silberholz, John (2018), "¿Qué funciona mejor cuando? Una evaluación sistemática de heurísticas para Max-Cut y QUBO", INFORMS Journal on Computing , 30 (3): 608–624, doi : 10.1287 / ijoc.2017.0798.
enlaces externos
- Pierluigi Crescenzi, Viggo Kann, Magnús Halldórsson, Marek Karpinski, Gerhard Woeginger (2000), "Maximum Cut" , en "Un compendio de problemas de optimización de NP" .
- Andrea Casini, Nicola Rebagliati (2012), "Una biblioteca de Python para resolver Max Cut"