corte máximo

Problema de encontrar un corte máximo en un gráfico.

Un ejemplo de corte máximo.

En 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 modo que el número de aristas entre S y T sea el mayor posible. Encontrar dicho corte 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 tal que el número de aristas entre S y el subconjunto complementario sea lo más grande posible. De manera equivalente, se quiere un subgrafo bipartito del gráfico con tantas aristas como sea posible.

Existe una versión más general del problema llamada max-cut ponderado , donde cada arista está asociada a un número real, su peso , y el objetivo es maximizar el peso total de las aristas entre S y su complemento en lugar del número de Los bordes. El problema de corte máximo ponderado que permite pesos positivos y negativos se puede transformar trivialmente en un problema de corte mínimo ponderado invirtiendo el signo en todos los pesos.

límites inferiores

Edwards ^{[1] [2]} obtuvo los siguientes dos límites inferiores para Max-Cut en un gráfico G con n vértices ym aristas (en (a) G es arbitrario, pero en (b) está conexo):

(a) ${\displaystyle \left\lceil {\frac {m}{2}}+{\sqrt {{\frac {m}{8}}+{\frac {1}{64}}}}-{\frac {1}{8}}\right\rceil }$

(b) ${\displaystyle {\frac {m}{2}}+{\frac {n-1}{4}}.}$

El encuadernado (b) a menudo se denomina encuadernado de Edwards-Erdős ^[3], como lo conjeturó Erdős. Edwards demostró el límite de Edwards-Erdős utilizando un método probabilístico; Crowston et al. ^[4] demostró el límite utilizando álgebra lineal y análisis de funciones pseudobooleanas.

La prueba de Crowston et al. nos permite extender el límite de Edwards-Erdős al problema del subgrafo equilibrado ( BSP ) ^[4] en gráficos con signo G = ( V , E , s ) , es decir, gráficos donde a cada arista se le asigna + o –. Para una partición de V en subconjuntos U y W , una arista xy está equilibrada si s ( xy ) = + y xey están en el mismo subconjunto, o s ( xy ) = – y xey son subconjuntos diferentes. BSP tiene como objetivo encontrar una partición con el número máximo b ( G ) de aristas equilibradas en G . El Edwards-Erdős da un límite inferior en b ( G ) para cada gráfico conectado con signo G . El límite (a) se mejoró para clases especiales de gráficos: gráficos sin triángulos, gráficos de grado máximo dado, gráficos sin H , etc., ver, por ejemplo, ^{[5] [6] [7]}

Poljak y Turzik ^[8] ampliaron el límite de Edwards-Erdős al Max-Cut ponderado:

${\displaystyle {\frac {w(G)}{2}}+{\frac {w(T_{min})}{4}},}$

donde w ( G ) yw ( T _min ) son los pesos de G y su árbol de expansión de peso mínimo T _min . Recientemente, Gutin y Yeo ^[9] obtuvieron una serie de límites inferiores para Max-Cut ponderado extendiendo el límite de Poljak-Turzik para gráficos ponderados arbitrarios y límites para clases especiales de gráficos ponderados.

Complejidad computacional

El siguiente problema de decisión relacionado con cortes máximos se ha estudiado ampliamente en informática teórica :

Dado un gráfico G y un número entero k , determine 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 demostrar presentando un recorte suficientemente grande. La completitud NP del problema se puede demostrar, por ejemplo, mediante una reducción de la satisfacibilidad máxima 2 (una restricción del problema de satisfacibilidad máxima ). ^[10] La versión ponderada del problema de decisión fue uno de los 21 problemas NP-completos de Karp ; ^[11] Karp demostró la completitud NP mediante una reducción del problema de partición .

La variante de optimización canónica del problema de decisión anterior generalmente se conoce como problema de corte máximo o corte máximo 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-difícil , no se conocen algoritmos de tiempo polinomial para Max-Cut en gráficos generales.

Graficos planos

Sin embargo, en los gráficos planos , el problema del corte máximo es dual al 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 conjunto de corte máximo de un gráfico G son los duales de las aristas que se duplican en un recorrido de inspección óptimo del gráfico dual de G . El recorrido de inspección óptimo forma una curva que se intersecta a sí misma y que separa el plano en dos subconjuntos, el subconjunto de puntos para los cuales el número de devanados de la curva es par y el subconjunto para los cuales el número de devanados es impar; estos dos subconjuntos forman un corte que incluye todas las aristas cuyos duales aparecen un número impar de veces en el recorrido. El problema de inspección de ruta se puede resolver en tiempo polinomial, y esta dualidad permite que el problema de corte máximo también se resuelva en tiempo polinomial para gráficos planos. ^[12] Sin embargo, se sabe que el problema de bisección máxima es NP-difícil. ^[13]

Algoritmos de aproximación

El problema Max-Cut es APX-duro , ^[14] lo que significa que no existe un esquema de aproximación en tiempo polinomial (PTAS), arbitrariamente cercano a la solución óptima, a menos que P = NP. Por lo tanto, cada algoritmo de aproximación de tiempo polinomial conocido logra una relación de aproximación estrictamente menor que uno.

Existe un algoritmo aleatorio simple de aproximación de 0,5 : para cada vértice, se lanza una moneda para decidir a qué mitad de la partición asignarla. ^{[15] [16]} Como se esperaba, la mitad de los bordes son bordes cortados. Este algoritmo puede ser desaleatorizado con el método de probabilidades condicionales ; por lo tanto, también existe un algoritmo determinista simple de aproximación de 0,5 en tiempo polinomial. ^{[17] [18]} Uno de esos 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 de la partición al otro, mejorando la solución en cada paso, hasta que no haya más mejoras. Se pueden fabricar de este tipo. El número de iteraciones es máximo porque el algoritmo mejora el corte en al menos un borde en cada paso. Cuando el algoritmo termina, al menos la mitad de las aristas incidentes en 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. ${\displaystyle G=(V,E)}$ ${\displaystyle |E|}$ ${\displaystyle |E|/2}$

El algoritmo de aproximación en 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 donde ${\displaystyle \alpha \approx 0.878,}$

${\displaystyle \alpha ={\frac {2}{\pi }}\min _{0\leq \theta \leq \pi }{\frac {\theta }{1-\cos \theta }}.}$^{[19] [20]}

Si la conjetura de los juegos únicos es cierta, esta es la mejor relación de aproximación posible para el corte máximo. ^[21] Sin tales suposiciones no comprobadas, se ha demostrado que es NP-difícil aproximar el valor de corte máximo con una relación de aproximación mejor que . ^{[22] [23]} ${\displaystyle {\tfrac {16}{17}}\approx 0.941}$

En ^[24] hay un análisis ampliado de 10 heurísticas para este problema, incluida la implementación de código abierto.

Algoritmos parametrizados y kernelización.

Si bien es trivial demostrar que el problema de encontrar un corte de tamaño al menos (el parámetro) k es manejable con parámetros fijos (FPT), es mucho más difícil demostrar la manejabilidad con parámetros fijos para el problema de decidir si un gráfico G tiene un corte de tamaño al menos el límite inferior de Edwards-Erdős (ver Límites inferiores arriba) más (el parámetro) k . Crowston et al. ^[25] demostró que el problema se puede resolver a tiempo y admite un núcleo de tamaño . Crowston et al. ^[25] extendieron el resultado de la trazabilidad de parámetros fijos al problema del subgrafo equilibrado (BSP, ver Límites inferiores arriba) y mejoraron el tamaño del núcleo a (también es válido para BSP). Etscheid y Mnich ^[26] mejoraron el resultado de la trazabilidad de parámetros fijos para BSP y el resultado del tamaño del kernel para los vértices. ${\displaystyle 8^{k}O(n^{4})}$ ${\displaystyle O(k^{5})}$ ${\displaystyle O(k^{3})}$ ${\displaystyle 8^{k}O(m)}$ ${\displaystyle O(k)}$

Aplicaciones

Aprendizaje automático

Al tratar sus nodos como características y sus bordes como distancias, el algoritmo de corte máximo divide un gráfico en dos subconjuntos bien separados. En otras palabras, se puede aplicar de forma natural para realizar una clasificación binaria . En comparación con los algoritmos de clasificación más comunes, no requiere un espacio de características, solo las distancias entre los elementos internos. ^[27]

Física teórica

En física estadística y sistemas desordenados , el problema de Max Cut equivale a minimizar el hamiltoniano de un modelo de vidrio giratorio , más simplemente el modelo de Ising . ^[28] Para el modelo de Ising en un gráfico G y solo interacciones con el vecino más cercano, el hamiltoniano es

${\displaystyle H[s]=-\sum _{ij\in E(G)}J_{ij}s_{i}s_{j}}$

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 se divide en dos conjuntos, aquellos con giro hacia arriba y aquellos con giro hacia abajo. Denotamos con el conjunto de aristas que conectan los dos conjuntos. Entonces podemos reescribir el hamiltoniano como ${\displaystyle s_{i}=\pm 1.}$ ${\displaystyle V(G)}$ ${\displaystyle V^{+}}$ ${\displaystyle V^{-}.}$ ${\displaystyle \delta (V^{+})}$

${\displaystyle {\begin{aligned}H[s]&=-\sum _{ij\in E(V^{+})}J_{ij}-\sum _{ij\in E(V^{-})}J_{ij}+\sum _{ij\in \delta (V^{+})}J_{ij}\\&=-\sum _{ij\in E(G)}J_{ij}+2\sum _{ij\in \delta (V^{+})}J_{ij}\\&=C+2\sum _{ij\in \delta (V^{+})}J_{ij}\end{aligned}}}$

Minimizar esta energía es equivalente al problema de corte mínimo o establecer los pesos del gráfico como el problema de corte máximo. ^[28] ${\displaystyle w_{ij}=-J_{ij},}$

Diseño de circuito

El problema del corte máximo tiene aplicaciones en el diseño VLSI . ^[28]

Ver también

• corte minimo
• Corte k mínimo
• Transversal de ciclo impar , equivalente a pedir el subgrafo inducido bipartito más grande
• Partición hostil , un concepto relacionado para gráficos infinitos

Notas

1. Edwards (1973).
2. Edwards (1975).
3. Bylka, Idzik y Tuza (1999).
4. Crowston et al. (2014).
5. Alon, Krivelevich y Sudakov (2005).
6. Scott (2005).
7. Zeng y Hou (2017).
8. Poljak y Turzik (1986).
9. Gutin y Yeo (2021).
10. Garey y Johnson (1979).
11. Karp (1972).
12. Hadlock (1975).
13. Jansen y col. (2005).
14. Papadimitriou y Yannakakis (1991) demuestran que MaxSNP está completo.
15. Mitzenmacher y Upfal (2005), secc. 6.2.
16. Motwani y Raghavan (1995), secc. 5.1.
17. Mitzenmacher y Upfal (2005), secc. 6.3.
18. Khuller, Raghavachari y Young (2007).
19. Gaur y Krishnamurti (2007).
20. Ausiello y col. (2003)
21. Khot y col. (2007).
22. Hastad (2001)
23. Trevisan y otros. (2000)
24. Dunning, Gupta y Silberholz (2018)
25. Crowston, Jones y Mnich (2015).
26. Etscheid y Mnich (2018).
27. Boykov, YY; Jolly, M.-P. (2001). "Recortes de gráficos interactivos para una segmentación óptima de límites y regiones de objetos en imágenes ND". Actas de la Octava Conferencia Internacional IEEE sobre Visión por Computadora. ICCV 2001 . vol. 1. Computación IEEE. Soc. págs. 105-112. doi :10.1109/iccv.2001.937505. ISBN 0-7695-1143-0. S2CID  2245438.
28. Barahona, Francisco; Grötschel, Martín; Jünger, Michael; Reinelt, Gerhard (1988). "Una aplicación de optimización combinatoria a la física estadística y el diseño de circuitos". La investigación de operaciones . 36 (3): 493–513. doi :10.1287/opre.36.3.493. ISSN  0030-364X. JSTOR  170992.

Referencias

• Alón, N.; Krivelevich, M.; Sudakov, B. (2005), "Maxcut en gráficos libres de H ", Combin. Probablemente. Computadora. , 14 : 629–647, doi : 10.1017/S0963548305007017, S2CID  123485000.
• 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 aproximabilidad , Springer.

El corte máximo (versión de optimización) es el problema ND14 en el Apéndice B (página 399).

• Bylka, S.; Idzik, A.; Tuza, I. (1999), "Recortes máximos: mejoras y análogos algorítmicos locales de la desigualdad de Edwards-Erd6s", Matemáticas discretas. , 194 : 39–58, doi : 10.1016/S0012-365X(98)00115-0.
• Crowston, R.; Compañeros, M.; Gutín, G.; Jones, M.; Kim, EJ; Rosamond, F.; Ruzsa, IZ; Thomassé, S.; Yeo, A. (2014), "Satisfacer más de la mitad de un sistema de ecuaciones lineales sobre GF (2): un enfoque multivariado", J. Comput. Sistema. Ciencia. , 80 (4): 687–696, doi : 10.1016/j.jcss.2013.10.002.
• Crowston, R.; Gutín, G.; Jones, M.; Muciaccia, G. (2013), "Problema de subgrafo equilibrado máximo parametrizado por encima del límite inferior", Theor. Computadora. Ciencia. , 513 : 53–64, arXiv : 1212.6848 , doi : 10.1016/j.tcs.2013.10.026.
• Crowston, R.; Jones, M.; Mnich, M. (2015), "Max-cut parametrizado por encima del límite Edwards-Erdős", Algorithmica , 72 (3): 734–757, doi :10.1007/s00453-014-9870-z, S2CID  14973734.
• Dunning, Iain; Gupta, Swati; Silberholz, John (2018), "¿Qué funciona mejor y cuándo? 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, S2CID  485706.
• Edwards, CS (1973), "Algunas propiedades extremas de subgrafos bipartitos", Can. J. Matemáticas. , 25 (3): 475–485, doi : 10.4153/CJM-1973-048-x , S2CID  121925638.
• Edwards, CS (1975), "Un límite inferior mejorado para el número de aristas en un subgrafo bipartito más grande", Avances recientes en teoría de grafos , págs..
• Etscheid, M.; Mnich, M. (2018), "Núcleos lineales y algoritmos de tiempo lineal para encontrar cortes grandes", Algorithmica , 80 (9): 2574–2615, doi : 10.1007/s00453-017-0388-z , hdl : 11420/4693 , S2CID  16301072.
• Garey, Michael R .; Johnson, David S. (1979), Computadoras e intratabilidad: una guía para la teoría de la integridad NP , 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 rounding and extensions", en González, Teófilo F. (ed.), Handbook of Approximation Algorithms and Metaheuristics , Chapman & Hall/CRC.
• Goemans, Michel X .; Williamson, David P. (1995), "Algoritmos de aproximación mejorados para problemas de satisfacibilidad y corte máximo utilizando programación semidefinida", Journal of the ACM , 42 (6): 1115–1145, doi : 10.1145/227683.227684 , S2CID  15794408.
• Gutín, G .; Yeo, A. (2021), "Límites inferiores para el corte ponderado máximo", arXiv : 2104.05536 [math.CO].
• 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), "Esquemas de aproximación de tiempo polinómico para MAX-BISECCIÓN en gráficos planos y geométricos", 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.), Complejidad de la computación informática , Plenum Press, págs. 85-103.
• Khot, Subhash ; Kindler, chico; Mossel, Eljanán; O'Donnell, Ryan (2007), "¿Resultados óptimos de inaproximabilidad para MAX-CUT y otros CSP de 2 variables?", SIAM Journal on Computing , 37 (1): 319–357, doi :10.1137/S0097539705447372, S2CID  2090495.
• Khuller, Samir; Raghavachari, Balaji; Young, Neal E. (2007), "Métodos codiciosos", en González, Teófilo F. (ed.), Manual de algoritmos y metaheurísticas de aproximación , 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.), Enciclopedia de algoritmos , 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), "Clases de optimización, aproximación y complejidad", Journal of Computer and System Sciences , 43 (3): 425–440, doi : 10.1016/0022-0000(91)90023-X.
• Poljak, S.; Turzik, Z. (1986), "Una heurística de tiempo polinomial para ciertos problemas de optimización de subgrafos con el límite del peor de los casos garantizado", Matemáticas discretas. , 58 (1): 99–104, doi : 10.1016/0012-365X(86)90192-5.
• Scott, A. (2005), "Particiones juiciosas y problemas relacionados", Encuestas en combinatoria, Serie de notas de conferencias de la London Mathematical Society , 327 : 95-117.
• Trevisan, Luca ; Sorkin, Gregorio; Sudán, Madhu; Williamson, David (2000), "Gadgets, aproximación y programación lineal", Actas del 37º Simposio IEEE sobre fundamentos de la informática : 617–626.
• Zeng, Q.; Hou, J. (2017), "Subgrafos bipartitos de gráficos libres de H ", Bull. Agosto. Matemáticas. Soc. , 30 (3): 1–13, doi :10.1017/S0004972716001295.

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 NP".
• Andrea Casini, Nicola Rebagliati (2012), "Una biblioteca de Python para resolver Max Cut"