Algoritmo de Karger

La operación fundamental del algoritmo de Karger es una variante de la contracción de aristas. El resultado de contraer la arista ${\displaystyle e=\{u,v\}}$ es un nuevo nodo ${\displaystyle uv}$. Cada arista ${\displaystyle \{w,u\}}$ o ${\displaystyle \{w,v\}}$ para ${\displaystyle w\notin \{u,v\}}$ hasta los extremos de la arista contraída se reemplaza por una arista ${\displaystyle \{w,uv\}}$ hasta el nuevo nodo. Finalmente, se eliminan los nodos contraídos ${\displaystyle u}$ y ${\displaystyle v}$ con todas sus aristas incidentes. En particular, el grafo resultante no contiene bucles propios. El resultado de contraer la arista ${\displaystyle e}$ se denota como ${\displaystyle G/e}$.

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

La idea clave del algoritmo es que es mucho más probable que las aristas que no son de corte mínimo se seleccionen aleatoriamente y se pierdan por contracción, ya que las aristas con corte mínimo suelen ser ampliamente superadas en número por las aristas que no son de corte mínimo. Posteriormente, es plausible que las aristas con corte mínimo sobrevivan a toda la contracción de aristas, y el algoritmo identificará correctamente la arista con corte mínimo.

   procedimiento contraer(${\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 utilizando una lista de adyacencia o una matriz de adyacencia, se puede utilizar una sola operación de contracción de aristas con un número lineal de actualizaciones a la estructura de datos, para un tiempo de ejecución total de ${\displaystyle O(|V|^{2})}$. Alternativamente, el procedimiento puede considerarse como una ejecución del algoritmo de Kruskal para construir el árbol recubridor mínimo en un grafo donde las aristas tienen pesos ${\displaystyle w(e_{i})=\pi (i)}$ según una permutación aleatoria ${\displaystyle \pi }$. Eliminar la arista más pesada de este árbol da como resultado dos componentes que describen un corte. De esta manera, el procedimiento de contracción se puede disponer como el algoritmo de Kruskal en el tiempo ${\displaystyle O(|E|\log |E|)}$.

Los desarrollos más conocidos utilizan ${\displaystyle O(|E|)}$ tiempo y espacio de memoria, o ${\displaystyle O(|E|\log |E|)}$ tiempo y ${\displaystyle O(|V|)}$ espacio, respectivamente.^[1]

En un grafo ${\displaystyle G=(V,E)}$ con ${\displaystyle n=|V|}$ vértices, el algoritmo de contracción devuelve un corte mínimo con una probabilidad polinómicomente pequeña, ${\displaystyle {\binom {n}{2}}^{-1}}$. Debe recordarse que todo grafo tiene ${\displaystyle 2^{n-1}-1}$ cortes (según lo explicado en la sección anterior), entre los cuales ${\displaystyle {\tbinom {n}{2}}}$ pueden ser, como máximo, 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, ${\displaystyle {\frac {\tbinom {n}{2}}{2^{n-1}-1}}}$.

Por ejemplo, un grafo ciclo con ${\displaystyle n}$ vértices tiene exactamente ${\displaystyle {\binom {n}{2}}}$ cortes mínimos, dados por cada elección de 2 aristas. El procedimiento de contracción encuentra cada uno de estos con la misma probabilidad.

Para establecer con mayor precisión el límite inferior de la probabilidad de éxito, sea ${\displaystyle C}$ el conjunto de las aristas con un corte mínimo específico de tamaño ${\displaystyle k}$. El algoritmo de contracción devuelve ${\displaystyle C}$ si ninguna de las aristas aleatorias eliminadas por el algoritmo pertenece al conjunto de cortes ${\displaystyle C}$. En particular, la primera contracción de arista evita ${\displaystyle C}$, lo que ocurre con una probabilidad de ${\displaystyle 1-k/|E|}$. El grado mínimo de ${\displaystyle G}$ es al menos ${\displaystyle k}$ (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 ${\displaystyle |E|\geqslant nk/2}$. Por lo tanto, la probabilidad de que el algoritmo de contracción elija una arista de ${\displaystyle C}$ es:

${\displaystyle {\frac {k}{|E|}}\leqslant {\frac {k}{nk/2}}={\frac {2}{n}}.}$

La probabilidad ${\displaystyle p_{n}}$ de que el algoritmo de contracción en un grafo de ${\displaystyle n}$-vértices evite ${\displaystyle C}$ satisface la recurrencia ${\displaystyle p_{n}\geqslant \left(1-{\frac {2}{n}}\right)p_{n-1}}$, con ${\displaystyle p_{2}=1}$, que puede expandirse como:

${\displaystyle p_{n}\geqslant \prod _{i=0}^{n-3}{\Bigl (}1-{\frac {2}{n-i}}{\Bigr )}=\prod _{i=0}^{n-3}{\frac {n-i-2}{n-i}}={\frac {n-2}{n}}\cdot {\frac {n-3}{n-1}}\cdot {\frac {n-4}{n-2}}\cdots {\frac {3}{5}}\cdot {\frac {2}{4}}\cdot {\frac {1}{3}}={\binom {n}{2}}^{-1}\,.}$

Al repetir el algoritmo de contracción ${\displaystyle T={\binom {n}{2}}\ln n}$ veces con elecciones aleatorias independientes y obtener 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 grafo con ${\displaystyle n}$ vértices y ${\displaystyle m}$ aristas es ${\displaystyle O(Tm)=O(n^{2}m\log n)}$.

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

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

   procedimiento contrato(${\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}}$ de que este procedimiento de contracción evite un corte específico ${\displaystyle C}$ en un grafo de ${\displaystyle n}$-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 menor que ${\displaystyle {\frac {1}{2}}}$ alrededor de ${\displaystyle t=n/{\sqrt {2}}}$. En particular, la probabilidad de que una arista de ${\displaystyle C}$ se contraiga aumenta 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(${\displaystyle G=(V,E)}$):
   si ${\displaystyle |V|\leq 6}$:
       devolver contrato(${\displaystyle G}$, ${\displaystyle 2}$)
   de lo contrario:
       ${\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 minfastmincut(${\displaystyle G_{1}}$), fastmincut(${\displaystyle G_{2}}$)

El parámetro de contracción ${\displaystyle t}$ se elige de modo que cada llamada a la contracción tenga una probabilidad de al menos la mitad de éxito (es decir, de evitar la contracción de una arista de un conjunto de corte específico ${\displaystyle C}$). Esto permite modelar la parte exitosa del árbol de recursión como un árbol binario aleatorio generado por un proceso de Galton-Watson crítico, y analizarlo en consecuencia.^[3]

La probabilidad ${\displaystyle P(n)}$ de que este árbol aleatorio de llamadas exitosas contenga una ruta lo suficientemente larga como para llegar a la base de la recursión y encontrar ${\displaystyle C}$ viene dada por la relación de recurrencia

${\displaystyle P(n)=1-\left(1-{\frac {1}{2}}P\left({\Bigl \lceil }1+{\frac {n}{\sqrt {2}}}{\Bigr \rceil }\right)\right)^{2}}$

con solución ${\displaystyle P(n)=\Omega \left({\frac {1}{\log n}}\right)}$. El tiempo de ejecución del corte rápido mínimo satisface que

${\displaystyle T(n)=2T\left({\Bigl \lceil }1+{\frac {n}{\sqrt {2}}}{\Bigr \rceil }\right)+O(n^{2})}$

con solución ${\displaystyle T(n)=O(n^{2}\log n)}$. Para alcanzar la probabilidad de error ${\displaystyle O(1/n)}$, el algoritmo puede repetirse ${\displaystyle O(\log n/P(n))}$ veces, para un tiempo de ejecución total de ${\displaystyle T(n)\cdot {\frac {\log n}{P(n)}}=O(n^{2}\log ^{3}n)}$. Esto supone una mejora de un orden de magnitud con respecto al algoritmo original de Karger.^[3]

Para determinar un corte mínimo, se debe tocar cada arista del grafo al menos una vez, lo que equivale a un tiempo ${\displaystyle \Theta (n^{2})}$ en un grafo denso. El algoritmo de corte mínimo de Karger-Stein requiere un tiempo de ejecución de ${\displaystyle O(n^{2}\ln ^{O(1)}n)}$, que es muy cercano a este.