El algoritmo de Karger

En informática y teoría de grafos , el algoritmo de Karger es un algoritmo aleatorio para calcular un corte mínimo de un grafo conexo . 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 una arista.${\displaystyle (u,v)}$en un grafo no dirigido${\displaystyle G=(V,E)}$. De manera informal, la contracción de una arista fusiona los nodos${\displaystyle u}$y${\displaystyle v}$en uno, reduciendo el número total de nodos del grafo en uno. Todos los demás bordes que conectan${\displaystyle u}$o${\displaystyle v}$se "reconectan" al nodo fusionado, produciendo efectivamente un multigrafo . El algoritmo básico de Karger contrae iterativamente aristas elegidas al azar hasta que solo quedan dos nodos; esos nodos representan un corte en el grafo original. Al iterar este algoritmo básico un número suficiente de veces, se puede encontrar un corte mínimo con alta probabilidad .

Un corte${\displaystyle (S,T)}$en un grafo no dirigido${\displaystyle G=(V,E)}$es una partición de los vértices${\displaystyle V}$en dos conjuntos no vacíos y disjuntos${\displaystyle S\cup T=V}$El conjunto de corte de un corte consta de los bordes${\displaystyle \{\,uv\in E\colon u\in S,v\in T\,\}}$entre las dos partes. El tamaño (o peso ) de un corte en un grafo no ponderado es la cardinalidad del conjunto de corte, es decir, el número de aristas entre las dos partes,

${\displaystyle w(S,T)=|\{\,uv\in E\colon u\in S,v\in T\,\}|\,.}$

Hay${\displaystyle 2^{|V|}}$formas de elegir para cada vértice si pertenece a${\displaystyle S}$o para${\displaystyle T}$, pero dos de estas opciones hacen${\displaystyle S}$o${\displaystyle T}$vacíos y no dan lugar a recortes. Entre las opciones restantes, intercambiar los roles de${\displaystyle S}$y${\displaystyle T}$no cambia el corte, por lo que cada corte se cuenta dos veces; por lo tanto, hay${\displaystyle 2^{|V|-1}-1}$cortes distintos. El problema del corte mínimo consiste en encontrar el corte de menor tamaño entre estos cortes.

Para grafos ponderados con pesos de arista positivos${\displaystyle w\dos puntos E\rightarrow \mathbf {R} ^{+}}$El peso del corte es la suma de los pesos de las aristas entre vértices en cada parte.

${\displaystyle w(S,T)=\sum _{uv\in E\colon u\in S,v\in T}w(uv)\,,}$

lo cual concuerda con la definición no ponderada de${\displaystyle w=1}$.

Un corte a veces se denomina “corte global” para distinguirlo de un “${\displaystyle s}$-${\displaystyle t}$cortar” para un par de vértices dado, lo cual tiene el requisito adicional de que${\displaystyle s\in S}$y${\displaystyle t\in T}$Cada recorte global es un${\displaystyle s}$-${\displaystyle t}$cortado para algunos${\displaystyle s,t\in V}$Por lo tanto, el problema del corte mínimo se puede resolver en tiempo polinomial iterando sobre todas las opciones de${\displaystyle s,t\in V}$y resolviendo el mínimo resultante${\displaystyle s}$-${\displaystyle t}$problema de corte utilizando el teorema de flujo máximo-corte mínimo y un algoritmo de tiempo polinomial para flujo máximo , como el algoritmo push-relabel , aunque este enfoque no es óptimo. Mejores algoritmos deterministas para el problema de corte mínimo global incluyen el algoritmo Stoer-Wagner , que tiene un tiempo de ejecución de${\displaystyle O(mn+n^{2}\log n)}$. ^{[ 2 ]}

La operación fundamental del algoritmo de Karger es una forma de contracción de aristas . El resultado de contraer la arista es...${\displaystyle e=\{u,v\}}$es un nodo nuevo${\displaystyle uv}$Cada borde${\displaystyle \{w,u\}}$o${\displaystyle \{w,v\}}$para${\displaystyle w\notin \{u,v\}}$Los extremos del borde contraído se reemplazan por un borde.${\displaystyle \{w,uv\}}$al nuevo nodo. Finalmente, los nodos contraídos ${\displaystyle u}$y${\displaystyle v}$con todos sus bordes incidentes eliminados. En particular, el grafo resultante no contiene bucles propios. El resultado de la contracción del borde${\displaystyle e}$se denota${\displaystyle G/e}$.

El algoritmo de contracción contrae repetidamente aristas aleatorias en el grafo, hasta que solo quedan dos nodos, momento en el que solo hay un único corte.

La idea clave del algoritmo es que es mucho más probable que los bordes que no son de corte mínimo se seleccionen aleatoriamente y se pierdan por contracción, ya que los bordes de corte mínimo suelen ser superados en número por los que no lo son. Por consiguiente, es plausible que los bordes de corte mínimo sobrevivan a toda la contracción de bordes, y el algoritmo los identificará correctamente.

contrato de procedimiento (${\displaystyle G=(V,E)}$): mientras${\displaystyle |V|>2}$ elegir${\displaystyle e\in E}$uniformemente al azar ${\displaystyle G\leftarrow G/e}$devolver el único corte en${\displaystyle G}$

Cuando el grafo se representa mediante listas de adyacencia o una matriz de adyacencia , se puede implementar una única operación de contracción de aristas con un número lineal de actualizaciones de la estructura de datos, para un tiempo de ejecución total de${\displaystyle O(|V|^{2})}$Alternativamente, el procedimiento puede verse como una ejecución del algoritmo de Kruskal para construir el árbol de expansión mínima en un grafo donde las aristas tienen pesos.${\displaystyle w(e_{i})=\pi (i)}$según una permutación aleatoria${\displaystyle \pi }$Al eliminar la arista más pesada de este árbol se obtienen dos componentes que describen un corte. De esta forma, el procedimiento de contracción se puede implementar como el algoritmo de Kruskal en tiempo${\displaystyle O(|E|\log |E|)}$.

Las implementaciones más conocidas utilizan${\displaystyle O(|E|)}$tiempo y espacio, o${\displaystyle O(|E|\log |E|)}$tiempo y${\displaystyle O(|V|)}$espacio, respectivamente. ^{[ 1 ]}

Repetir el algoritmo de contracción

Al repetir el algoritmo de contracción${\displaystyle T={\binom {n}{2}}\ln n}$veces con elecciones aleatorias independientes y devolviendo el corte más pequeño, la probabilidad de no encontrar un corte mínimo es

${\displaystyle \left[1-{\binom {n}{2}}^{-1}\right]^{T}\leq {\frac {1}{e^{\ln n}}}={\frac {1}{n}}\,.}$

El tiempo total de ejecución para${\displaystyle T}$repeticiones para un gráfico con${\displaystyle n}$vértices y${\displaystyle m}$bordes es${\displaystyle O(Tm)=O(n^{2}m\log n)}$.

Una extensión del algoritmo de Karger, realizada por David Karger y Clifford Stein, logra una mejora de un orden de magnitud. ^{[ 3 ]}

La idea básica es realizar el procedimiento de contracción hasta que la gráfica alcance${\displaystyle t}$vértices.

contrato de procedimiento (${\displaystyle G=(V,E)}$,${\displaystyle t}$): mientras${\displaystyle |V|>t}$ elegir${\displaystyle e\in E}$uniformemente al azar ${\displaystyle G\leftarrow G/e}$devolver${\displaystyle G}$

La probabilidad${\displaystyle p_{n,t}}$que este procedimiento de contracción evita un corte específico${\displaystyle C}$en un${\displaystyle n}$-grafo de vértices es

${\displaystyle p_{n,t}\geq \prod _{i=0}^{n-t-1}{\Bigl (}1-{\frac {2}{n-i}}{\Bigr )}={\binom {t}{2}}{\Bigg /}{\binom {n}{2}}\,.}$

Esta expresión es aproximadamente${\displaystyle t^{2}/n^{2}}$y se vuelve menos que${\displaystyle {\frac {1}{2}}}$alrededor${\displaystyle t=n/{\sqrt {2}}}$. En particular, la probabilidad de que una arista de${\displaystyle C}$La contracción aumenta hacia el final. Esto justifica la idea de cambiar a un algoritmo más lento después de un cierto número de pasos de contracción.

procedimiento fastmincut(${\displaystyle G=(V,E)}$): si${\displaystyle |V|\leq 6}$: devolver contrato(${\displaystyle G}$,${\displaystyle 2}$) demás : ${\displaystyle t\leftarrow \lceil 1+|V|/{\sqrt {2}}\rceil }$${\displaystyle G_{1}\leftarrow }$contrato(${\displaystyle G}$,${\displaystyle t}$) ${\displaystyle G_{2}\leftarrow }$contrato(${\displaystyle G}$,${\displaystyle t}$) devolver min{fastmincut(${\displaystyle G_{1}}$), corte mínimo rápido(${\displaystyle G_{2}}$)}