Corte máximo

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

Un ejemplo de un corte máximo

En un grafo , 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 grafo 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 el problema del corte máximo .

El problema se puede plantear de forma sencilla de la siguiente manera: se desea un subconjunto S del conjunto de vértices tal que el número de aristas entre S y el subconjunto complementario sea el mayor posible. De forma equivalente, se desea un subgrafo bipartito del grafo con el mayor número posible de aristas.

Existe una versión más general del problema llamada corte máximo ponderado , donde cada arista está asociada con 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 aristas. El problema de corte máximo ponderado que permite pesos tanto positivos como negativos se puede transformar de manera trivial 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 y m aristas (en (a) G es arbitrario, pero en (b) es 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 límite (b) se denomina a menudo límite de Edwards-Erdős ^[3], ya que Erdős lo conjeturó. Edwards demostró el límite de Edwards-Erdős utilizando el método probabilístico; Crowston et al. ^[4] demostraron 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 grafos con signo G = ( V , E , s ) , es decir grafos 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 x e y están en el mismo subconjunto, o s ( xy ) = – y x e y son subconjuntos diferentes. El 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 grafo con signo conectado G . El límite (a) se mejoró para clases especiales de grafos: grafos sin triángulos, grafos de grado máximo dado, grafos sin H , etc., véase, por ejemplo, ^{[5] [6] [7]}

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

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

donde w ( G ) y w ( 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 ha sido ampliamente estudiado en la informática teórica :

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

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

Gráficos planares

Sin embargo, en los grafos planares , 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 grafo al menos una vez), en el sentido de que los bordes que no pertenecen a un conjunto de corte máximo de un grafo G son los duales de los bordes que se duplican en un recorrido de inspección óptimo del grafo dual de G. El recorrido de inspección óptimo forma una curva autointersecante que separa el plano en dos subconjuntos, el subconjunto de puntos para los cuales el número de vueltas de la curva es par y el subconjunto para el cual el número de vueltas 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 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 grafos planares. ^[12] Sin embargo, se sabe que el problema de bisección máxima es NP-duro. ^[13]

Algoritmos de aproximación

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

Hay un algoritmo simple de aproximación aleatoria de 0,5 : para cada vértice, lanza una moneda para decidir a qué mitad de la partición asignarlo. ^{[15] [16]} En expectativa, la mitad de los bordes son bordes cortados. Este algoritmo se puede desaleatorizar con el método de probabilidades condicionales ; por lo tanto, también hay un algoritmo simple de aproximación de 0,5 en tiempo polinomial determinista. ^{[17] [18]} Uno de estos algoritmos comienza con una partición arbitraria de los vértices del grafo 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 se puedan hacer más mejoras de este tipo. El número de iteraciones es como 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 los bordes incidentes a cada vértice pertenecen al corte, ya que de lo contrario mover el vértice mejoraría el corte. Por lo tanto, el corte incluye al menos bordes. ${\displaystyle G=(V,E)}$ ${\displaystyle |E|}$ ${\displaystyle |E|/2}$

El algoritmo de aproximación de tiempo polinomial para Max-Cut con la relación de aproximación mejor 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 verdadera, esta es la mejor razón de aproximación posible para el corte máximo. ^[21] Sin tales suposiciones no probadas, se ha demostrado que es NP-difícil aproximar el valor de corte máximo con una razón de aproximación mejor que . ^{[22] [23]} ${\displaystyle {\tfrac {16}{17}}\approx 0.941}$

En ^[24] hay un análisis extendido 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 manejabilidad con parámetros fijos para el problema de decidir si un grafo 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] demostraron que el problema se puede resolver en el tiempo y admite un núcleo de tamaño . Crowston et al. ^[25] extendieron el resultado de manejabilidad con parámetros fijos al Problema del Subgrafo Balanceado (BSP, ver Límites inferiores arriba) y mejoraron el tamaño del núcleo a (se cumple también para BSP). Etscheid y Mnich ^[26] mejoraron el resultado de manejabilidad con parámetros fijos para BSP a y el resultado del tamaño del núcleo a 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 grafo 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 dentro de él. ^[27]

Física teórica

En física estadística y sistemas desordenados , el problema de corte máximo es equivalente a minimizar el hamiltoniano de un modelo de vidrio de espín , más simplemente el modelo de Ising . ^[28] Para el modelo de Ising en un gráfico G y solo interacciones de vecinos más cercanos, el hamiltoniano es

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

Aquí cada vértice i del grafo es un sitio de espín que puede tomar un valor de espín. Una configuración de espín se divide en dos conjuntos, aquellos con espín hacia arriba y aquellos con espín hacia abajo. Denotamos con el conjunto de aristas que conectan los dos conjuntos. Podemos entonces 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 circuitos

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

Véase también

• Corte mínimo
• Corte k mínimo
• Ciclo impar transversal , equivalente a pedir el subgrafo inducido bipartito más grande
• Partición hostil , un concepto relacionado con los gráficos infinitos

Notas

1. Edwards (1973).
2. Edwards (1975).
3. Bylka, Idzik y Tuza (1999).
4. Crowston y otros (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. Carp (1972).
12. Hadlock (1975).
13. Jansen y otros (2005).
14. Papadimitriou y Yannakakis (1991) demuestran que MaxSNP está completo.
15. Mitzenmacher y Upfal (2005), Sec. 6.2.
16. Motwani y Raghavan (1995), secc. 5.1.
17. Mitzenmacher y Upfal (2005), Sec. 6.3.
18. Khuller, Raghavachari y Young (2007).
19. Gaur y Krishnamurti (2007).
20. Ausiello y otros (2003)
21. Khot y otros (2007).
22. Hasta (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). "Cortes de gráficos interactivos para la 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 Computador. ICCV 2001. Vol. 1. IEEE Comput. Soc. págs. 105–112. doi :10.1109/iccv.2001.937505. ISBN 0-7695-1143-0.S2CID2245438  .​
28. Barahona, Francisco; Grötschel, Martin; Jünger, Michael; Reinelt, Gerhard (1988). "Una aplicación de la optimización combinatoria a la física estadística y al diseño de circuitos". Investigación de operaciones . 36 (3): 493–513. doi :10.1287/opre.36.3.493. ISSN  0030-364X. JSTOR  170992.

Referencias

• Alon, N.; Krivelevich, M.; Sudakov, B. (2005), "Maxcut en grafos sin H ", Combin. Probab. Comput. , 14 : 629–647, doi :10.1017/S0963548305007017 (inactivo 2024-09-25), S2CID  123485000{{citation}}: CS1 maint: DOI inactive as of September 2024 (link).
• 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), "Cortes máximos: mejoras y análogos algorítmicos locales de la desigualdad de Edwards-Erd6s", Discrete Math. , 194 (1–3): 39–58, doi : 10.1016/S0012-365X(98)00115-0.
• Crowston, R.; Fellows, M.; Gutin, 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. Syst. Sci. , 80 (4): 687–696, doi : 10.1016/j.jcss.2013.10.002.
• Crowston, R.; Gutin, G.; Jones, M.; Muciaccia, G. (2013), "Problema de subgrafo máximo equilibrado parametrizado por encima del límite inferior", Theor. Comput. Sci. , 513 : 53–64, arXiv : 1212.6848 , doi : 10.1016/j.tcs.2013.10.026.
• Crowston, R.; Jones, M.; Mnich, M. (2015), "Corte máximo parametrizado por encima del límite de 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. Math. , 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. 167-181.
• 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 NP-completitud , 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), "Redondeo y extensiones de LP", en Gonzalez, Teofilo 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 corte máximo y satisfacibilidad utilizando programación semidefinida", Journal of the ACM , 42 (6): 1115–1145, doi : 10.1145/227683.227684 , S2CID  15794408.
• Gutin, 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 de inaproximabilidad óptima", 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 temporal polinómica para MAX-BISECTION 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, Guy; Mossel, Elchanan; O'Donnell, Ryan (2007), "¿Resultados de inaproximabilidad óptimos 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 voraces", en Gonzalez, Teofilo F. (ed.), Handbook of Approximation Algorithms and Metaheuristics , 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), "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.
• Poljak, S.; Turzik, Z. (1986), "Una heurística de tiempo polinomial para ciertos problemas de optimización de subgrafos con límite garantizado para el peor caso", Discrete Math. , 58 (1): 99–104, doi : 10.1016/0012-365X(86)90192-5.
• Scott, A. (2005), "Particiones juiciosas y problemas relacionados", Encuestas sobre combinatoria, London Mathematical Society Lecture Note Series , 327 : 95–117.
• Trevisan, Luca ; Sorkin, Gregory; Sudan, 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 grafos libres de H ", Bull. Aust. Math. 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"