En informática y teoría de grafos , el algoritmo de Karger es un algoritmo aleatorio para calcular un corte mínimo de un gráfico conectado . Fue inventado por David Karger y publicado por primera vez en 1993. [1]
La idea del algoritmo se basa en el concepto de contracción de un borde. en un gráfico no dirigido . Hablando informalmente, la contracción de un borde fusiona los nodos y en uno, reduciendo el número total de nodos del gráfico en uno. Todos los demás bordes que conectan o se "vuelven a unir" al nodo fusionado, produciendo efectivamente un multigraph . El algoritmo básico de Karger contrae iterativamente los bordes elegidos al azar hasta que solo quedan dos nodos; esos nodos representan un corte en el gráfico original. Al iterar este algoritmo básico un número suficiente de veces, se puede encontrar un corte mínimo con alta probabilidad.
El problema global del corte mínimo
Un corte en un gráfico no dirigido es una partición de los vértices en dos conjuntos no vacíos e inconexos . El corte de un corte consta de los bordesentre las dos partes. El tamaño (o peso ) de un corte en un gráfico no ponderado es la cardinalidad del corte, es decir, el número de bordes entre las dos partes,
Existen formas de elegir para cada vértice si pertenece a o para , pero dos de estas opciones hacen o vacíos y no dar lugar a cortes. Entre las opciones restantes, intercambiar los roles de y no cambia el corte, por lo que cada corte se cuenta dos veces; por lo tanto, haycortes distintos. El problema de corte mínimo es encontrar un corte de menor tamaño entre estos cortes.
Para gráficos ponderados con pesos de bordes positivos el peso del corte es la suma de los pesos de los bordes entre los vértices de cada parte
que concuerda con la definición no ponderada de .
En ocasiones, un corte se denomina "corte global" para distinguirlo de un "- cut "para un par de vértices dado, que tiene el requisito adicional de que y . Cada corte global es un- corte para algunos . Por lo tanto, el problema de corte mínimo se puede resolver en tiempo polinomial iterando sobre todas las opciones de y resolviendo el mínimo resultante -problema de corte utilizando el teorema de corte mínimo de flujo máximo y un algoritmo de tiempo polinomial para el flujo máximo , como el algoritmo de empujar-volver a etiquetar , aunque este enfoque no es óptimo. Los mejores algoritmos deterministas para el problema de corte mínimo global incluyen el algoritmo de Stoer-Wagner , que tiene un tiempo de ejecución de. [2]
Algoritmo de contracción
La operación fundamental del algoritmo de Karger es una forma de contracción del borde . El resultado de contraer el borde es nuevo nodo . Cada borde o por hasta los puntos finales del borde contraído se reemplaza por un borde al nuevo nodo. Finalmente, los nodos contraídos y con todos sus bordes incidentes se eliminan. En particular, el gráfico resultante no contiene bucles propios. El resultado de contraer el borde se denota .
El algoritmo de contracción contrae repetidamente bordes aleatorios en el gráfico, hasta que solo quedan dos nodos, momento en el que solo hay un corte.
contrato de procedimiento): mientras escoger uniformemente al azar devuelve el único corte en
Cuando el gráfico se representa mediante listas de adyacencia o una matriz de adyacencia , se puede implementar una operación de contracción de un solo borde con un número lineal de actualizaciones de la estructura de datos, para un tiempo de ejecución total de. Alternativamente, el procedimiento puede verse como una ejecución del algoritmo de Kruskal para construir el árbol de expansión mínimo en un gráfico donde los bordes tienen pesos. según una permutación aleatoria . Eliminar el borde más pesado de este árbol da como resultado dos componentes que describen un corte. De esta manera, el procedimiento de contracción se puede implementar como el algoritmo de Kruskal en el tiempo..
Las implementaciones más conocidas utilizan tiempo y espacio, o tiempo y espacio, respectivamente. [1]
Probabilidad de éxito del algoritmo de contracción
En un grafico con vértices, el algoritmo de contracción devuelve un corte mínimo con una probabilidad polinomialmente pequeña . Cada gráfico tienecortes, [3] entre los cuales como máximopueden ser cortes mínimos. Por lo tanto, la probabilidad de éxito de este algoritmo es mucho mejor que la probabilidad de elegir un corte al azar, que es como máximo.
Por ejemplo, el gráfico de ciclo en vértices tiene exactamente cortes mínimos, dados por cada elección de 2 bordes. El procedimiento de contracción encuentra cada uno de estos con la misma probabilidad.
Para establecer aún más el límite inferior de la probabilidad de éxito, sea denotar los bordes de un corte mínimo específico de tamaño . Vuelve el algoritmo de contracción si ninguno de los bordes aleatorios pertenece al conjunto de cortes de . En particular, la contracción del primer borde evita, que pasa con probabilidad . El grado mínimo de Por lo menos (de lo contrario, un vértice de grado mínimo induciría un corte más pequeño donde una de las dos particiones contiene solo el vértice de grado mínimo), por lo que . Por lo tanto, la probabilidad de que el algoritmo de contracción elija una arista de es
La probabilidad que el algoritmo de contracción en un -El gráfico de vértice evita satisface la recurrencia , con , que se puede expandir como
Repitiendo el algoritmo de contracción
Repitiendo el algoritmo de contracción veces con elecciones aleatorias independientes y devolviendo el corte más pequeño, la probabilidad de no encontrar un corte mínimo es
El tiempo total de ejecución de repeticiones para un gráfico con vértices y bordes es .
Algoritmo de Karger-Stein
Una extensión del algoritmo de Karger debido a David Karger y Clifford Stein logra una mejora de un orden de magnitud. [4]
La idea básica es realizar el procedimiento de contracción hasta que la gráfica alcance vértices.
contrato de procedimiento, ): mientras escoger uniformemente al azar regreso
La probabilidad que este procedimiento de contracción evita un corte específico en un -El gráfico de vértice es
Esta expresión es aproximadamente y se vuelve menos que alrededor . En particular, la probabilidad de que una ventaja dese contrae crece hacia el final. Esto motiva la idea de cambiar a un algoritmo más lento después de un cierto número de pasos de contracción.
procedimiento fastmincut): si : return mincut ( ) más : contrato( , ) contrato( , ) return min {fastmincut ( ), fastmincut ( )}
Análisis
La probabilidad el algoritmo encuentra un corte específico viene dada por la relación de recurrencia
con solución . El tiempo de ejecución de fastmincut satisface
con solución . Para lograr la probabilidad de error, el algoritmo se puede repetir veces, para un tiempo de ejecución total de . Esta es una mejora de un orden de magnitud con respecto al algoritmo original de Karger.
Límite de mejora
Para determinar un corte mínimo, uno tiene que tocar cada borde en el gráfico al menos una vez, que es tiempo en un gráfico denso . El algoritmo de corte mínimo de Karger-Stein toma el tiempo de ejecución de, que está muy cerca de eso.
Referencias
- ↑ a b Karger, David (1993). "Min-cortes globales en RNC y otras ramificaciones de un algoritmo de Mincut simple" . Proc. 4to Simposio Anual ACM-SIAM sobre Algoritmos Discretos .
- ^ Stoer, M .; Wagner, F. (1997). "Un simple algoritmo min-cut". Revista de la ACM . 44 (4): 585. doi : 10.1145 / 263867.263872 .
- ^ Patrignani, Maurizio; Pizzonia, Maurizio (2001), "La complejidad del problema de los cortes coincidentes", en Brandstädt, Andreas ; Le, Van Bang (eds.), Graph-Theoretic Concepts in Computer Science: 27th International Workshop, WG 2001, Boltenhagen, Alemania, 14-16 de junio de 2001, Actas , Lecture Notes in Computer Science, 2204 , Berlín: Springer, págs. 284–295, doi : 10.1007 / 3-540-45477-2_26 , MR 1905640.
- ^ Karger, David R .; Stein, Clifford (1996). "Un nuevo enfoque al problema de corte mínimo" (PDF) . Revista de la ACM . 43 (4): 601. doi : 10.1145 / 234533.234534 .