Algoritmo de Karger

La versión actual de la página aún no ha sido revisada por colaboradores experimentados y puede diferir significativamente de la versión revisada el 28 de mayo de 2022; las comprobaciones requieren 3 ediciones .

Algoritmo de Karger
El gráfico y sus dos cortes. El corte rojo cruza tres aristas y el verde corta dos. Este último es uno de los cortes mínimos de este gráfico.
Lleva el nombre de	David Karger [d]
objetivo	encontrar el corte más pequeño de un gráfico
Estructura de datos	grafico
Tiempo promedio	$O(Tm)=O(n^{2}m\log n)$
costo de memoria	-

El algoritmo de Karger , en informática y teoría de grafos, es un algoritmo probabilístico que le permite encontrar el corte mínimo de un gráfico conectado . Algoritmo inventado por David Karger y publicado en 1993 [1] .

La idea del algoritmo se basa en la contracción de aristas en un grafo no dirigido. Durante la contracción del borde, dos vértices se fusionan en uno, lo que reduce el número de vértices del gráfico en uno. Todos los bordes de los vértices contraídos están conectados al vértice recién formado, generando un multigrafo . El algoritmo de Karger selecciona iterativamente bordes aleatorios y realiza la operación hasta que quedan dos vértices, que son un corte del gráfico original. Si el algoritmo se repite suficientes veces, entonces el corte mínimo se puede encontrar con alta probabilidad.

Descripción

Ejemplos

La tarea principal es encontrar cuellos de botella en varias redes. Ejemplos:

Descubrimiento de comunidades en redes sociales [2] .
Determinar las vulnerabilidades de un potencial adversario para destruir su red de transporte .
Segmentación de imágenes [3] [4] .

Algoritmo

La operación básica del algoritmo de Karger es una forma de contracción de borde . Para realizar esta operación en un borde arbitrario , los vértices del gráfico y se fusionan en uno . Si se elimina un vértice , cada borde de vista se reemplaza por un borde de vista . Los bucles se eliminan y, después de esta operación, el gráfico no contiene bucles. La función de costo se redefine de la siguiente manera: . $e=\{u,v\}$ $tu$ $v$ $ultravioleta$ $v$ ${\ estilo de visualización \ {v, x \}}$ ${\ estilo de visualización \ {u, x \}}$ $c'(e)={\begin{cases}c(e),&u,v\notin e\\c(e),&e=(x,u)\land (x,v)\notin E \\c((x,v)),&e\neq (x,u)\land (x,v)\en E\\c(e)+c((x,v)),&e=(x, u)\land (x,v)\in E\end{casos}}$

El algoritmo es una elección equiprobable de una arista aleatoria disponible y una unión de vértices según la operación descrita. El resultado del algoritmo es un par de vértices, el conjunto de aristas entre los cuales es una sección del gráfico. Este corte puede no ser mínimo, pero la probabilidad de que este corte sea mínimo es significativamente mayor que para un corte seleccionado al azar.

Pseudocódigo

El algoritmo de Karger repite n − 2 veces selecciona aleatoriamente la arista e reduce la arista e resulta el número de aristas entre los dos últimos vértices

Evidencia

Lema 1. . $\mathbb {Pr} [e_{i}\notin K\mid \bigcap _{1\leqslant j<i}e_{j}\notin K]\geqslant 1-{\frac {2}{n- yo+1}}$

Prueba. Tenga en cuenta que cada corte corresponde a un corte en . Sea , y . Entonces son válidas las siguientes diferencias: , (siempre que ) y . Por lo tanto ${\ Displaystyle H_ {j}}$ $GRAMO$ $k=|K|$ $n_{j}=|V(H_{j})|$ $m_{j}=|E(H_{j})|$ $n_{i-1}=n-i+1$ $m_{i-1}\geqslant k\cdot n_{i-1}/2$ $k\leqslant\delta (H_{i-1})$ ${\displaystyle \mathbb {Pr} [e_{i}\in K]={\frac {k}{m_{i-1))))$ $\mathbb {Pr} [e_{i}\notin K\mid \bigcap _{1\leqslant j<i}e_{j}\notin K]={\frac {k}{m_{i-1 ))}\geqslant {\frac {2}{n_{i-1}}}=1-{\frac {2}{n-i+1}}$

Lema 2. La probabilidad de que el resultado del algoritmo sea el corte más pequeño es mayor o igual a . ${\tbinom{n}{2}}^{-1}$

Prueba. Sea el -ésimo borde contraído siempre que . Además, sean y las gráficas después de la -ésima contracción, y cualquier corte más pequeño de la gráfica . Entonces lo siguiente es cierto: $e_{yo}$ $i$ ${\ estilo de visualización 1 \ leqslant i \ leqslant n-2}$ $H_{0}=G$ $Hola$ $i$ $k$ $GRAMO$

{\begin{alineado}\mathbb {Pr} [C{\text{ es un min.  Cortar}}]&\geqslant \mathbb {Pr} [C=K]\\&=\mathbb {Pr} [\bigcap _{1\leqslant i\leqslant n-2}e_{i}\notin K]\ \&=\prod _{1\leqslant i\leqslant n-2}\mathbb {Pr} [e_{i}\notin K\mid \bigcap _{1\leqslant j<i}e_{j}\notin K ]\\&\geqslant \prod _{1\leqslant i\leqslant n-2}(1-{\frac {2}{n-i+1)))\\&=\prod _{1\leqslant i \leqslant n-2}{\frac {ni-1}{n-i+1}}\\&={\frac {n-2}{n}}\cdot {\frac {n-3}{n -1}}\cdot \dots \cdot {\frac {2}{4}}\cdot {\frac {1}{3}}\\&={\frac {2}{n(n-1)} }={\tbinom {n}{2}}^{-1}\\\end{alineado}}

Algoritmo de Karger-Stein

Tenga en cuenta que la probabilidad de no encontrar el corte más pequeño con repeticiones es . Por lo tanto, es posible reducir arbitrariamente la probabilidad de error, pero esto aumentará el tiempo de ejecución del algoritmo. Para la constante de probabilidad de error, basta con ejecutar el algoritmo una vez y el tiempo de ejecución aumentará a . Una vez que se alcanza la probabilidad de error constante, disminuirá exponencialmente en función de . Hasta ahora, el algoritmo ha generado los cortes más pequeños posibles de forma independiente en cada llamada, pero los resultados de las fusiones del primer borde se pueden usar para muchas ejecuciones. La idea del algoritmo de Karger-Stein es identificar dos candidatos de contracción en cada iteración y continuar recursivamente el algoritmo de Karger para cada uno de ellos: $t\cdot {\tbinom {n}{2))$ $(1-{\tbinom {n}{2}}^{-1})^{t\cdot {\tbinom {n}{2}}}\leqslant (1/e)^{t}$ ${\tbinom {n}{2))$ $O(n^{4})$ $t$

Dana y . $G=(V,E)$ ${\displaystyle c\colon E\to \mathbb {N} ^{+))$
Si , encuentre el corte más pequeño y envíelo, termine el trabajo. $|V|\leqslant 6$ ${\ estilo de visualización C_ {U}}$
instalar _ $t=\lceil 1+{\frac {n}{\sqrt {2))}\rceil$
instalar _ ${\ estilo de visualización H = H' = G}$
Tire de las costillas hacia adentro . ${\ Displaystyle nt}$ $H$
Tire de las costillas hacia adentro . ${\ Displaystyle nt}$ $H'$
Calcular recursivamente los cortes más pequeños y . ${\ estilo de visualización C_ {H}}$ ${\ Displaystyle C_ {H'))$
Da salida al corte más pequeño o . ${\ estilo de visualización C_ {H}}$ ${\ Displaystyle C_ {H'))$

Teorema. El algoritmo de Karger-Stein tiene complejidad temporal . $O(n^{2}\cdot \log n)$

Prueba. La siguiente ecuación recursiva simplificada describe el tiempo de ejecución del algoritmo: for y for . La profundidad de recurrencia es , ya que el tamaño de los datos de entrada se reduce un número constante de veces. Sea al nivel de recursividad . Tenga en cuenta que en el nivel de recursividad, es necesario ejecutar el algoritmo una vez y el tamaño del gráfico de entrada para cada llamada recursiva es . Por lo tanto, el tiempo de ejecución de cada llamada recursiva es , y el tiempo de ejecución requerido dentro de la profundidad de recursión es . El tiempo total de ejecución es . $T(n)=2\cdot T(\lceil 1+{\frac {n}{\sqrt {2}}}\rceil )+O(n^{2})$ ${\ estilo de visualización n> 6}$ ${\ estilo de visualización T (n) = O (1)}$ $n\leqslant 6$ $D=O(\log n)$ $n_{l}=|V(H)|$ $l\geqslant 0$ $yo$ $2^l$ ${\displaystyle n_{l}\equiv {\frac {n}{({\sqrt {2)))^{l))))$ $O(n_{l}^{2})=O({\frac {n^{2}}{2^{l}}})$ $2^{l}\cdot O({\frac {n^{2}}{2^{l}}})=O(n^{2})$ $O(n^{2}\cdot \log n)$

Lema. . $p(t)\geqslant {\frac {1}{t+1))$

Prueba.

{\begin{alineado}p(t)&\geqslant 1-(1-p(t-1)/2)^{2}\\&\geqslant 1-(1-{\frac {1} {2t)))^{2}\\&={\frac {1}{t}}-{\frac {1}{4t^{2}}}\\&={\frac {4t-1} {4t^{2}}}\\&={\frac {(4t-1)(t+1)}{4t^{2}}}\cdot {\frac {1}{t+1}}\ \&={\frac {4t^{2}+4t-t-1}{4t^{2}}}\cdot {\frac {1}{t+1}}\\&\geqslant {\frac { 1}{t+1}}\end{alineado}}

Teorema. El algoritmo calcula el corte más pequeño con probabilidad . $\Omega (1/\log n)$

Prueba. Sea el corte más pequeño en el gráfico y . Entonces la probabilidad de que se conserve después de las contracciones es igual al mínimo: $k$ $k=|K|$ $k$ ${\ Displaystyle nt}$

{\begin{alineado}\prod_{1\leqslant i\leqslant nt}(1-{\frac {2}{n-i+1)))&=\prod_{1\leqslant i\ leqslant nt}({\frac {ni-1}{n-i+1)))\\&={\frac {n-2}{n}}\cdot {\frac {n-3}{n- 1}}\cdot \dots \cdot {\frac {t}{t+2}}\cdot {\frac {t-1}{t+1}}\\&={\frac {t(t-1 )) )}{n(n-1)))\\&={\frac {\lceil 1+n/{\sqrt {2))\rceil \cdot \lceil n/{\sqrt {2))\ rceil } {n(n-1)}}\\&\geqslant {\frac {1}{2}}\\\end{alineado}}

La probabilidad de que o tenga el mismo corte más pequeño que y sea al menos . El algoritmo de Karger-Stein solo tendrá éxito en dos casos: si o contiene un corte de tamaño mínimo y la llamada recursiva del algoritmo tiene éxito. Sea la probabilidad de que el algoritmo sea exitoso para el gráfico . Entonces la probabilidad de que el algoritmo se complete con éxito es . Sea la probabilidad de que el algoritmo tenga éxito en el nivel de recursión . Entonces de hecho si y . De ello se deduce que , donde es la profundidad de recursión. $H$ $H'$ $GRAMO$ ${\frac{1}{2))$ $H$ $H'$ $k$ $P(G')$ $GRAMO'$ $P(G)\geqslant 1-(1-P(H)/2)\cdot (1-P(H')/2)$ $pag(t)$ $t$ ${\displaystyle p(t)\geqslant 1-(1-p(t-1)/2)^{2))$ $t\geqslant 1$ ${\ estilo de visualización p (0) = 1}$ $p(t)\geqslant {\frac {1}{t+1))$ $P(G)=p(D)\geqslant {\frac {1}{D+1}}=\Omega ({\frac {1}{\log n)))$ $D=O(\log n)$

Después de reiniciar el algoritmo una vez, obtenemos el tiempo de ejecución y la probabilidad de error . $O(\log n)$ $O(n^{2}\log^{2}n)$ ${\ estilo de visualización \ Omega (1)}$

Véase también

Algoritmo de Stöhr-Wagner

Notas

↑ Karger, David R. Global Min-cuts in RNC, and Other Ramifications of a Simple Min-Cut Algorithm // SODA : journal. - 1993. - vol. 93 . - P. 21-30 . - ISBN 0-89871-313-7 .
^ Detección de comunidad mejorada de conjunto de terminales en redes sociales . Consultado el 24 de agosto de 2016. Archivado desde el original el 9 de julio de 2016. (indefinido)
↑ Problema de corte mínimo . Consultado el 24 de agosto de 2016. Archivado desde el original el 28 de agosto de 2016. (indefinido)
↑ Algoritmos aleatorios, tercera parte . Consultado el 24 de agosto de 2016. Archivado desde el original el 28 de mayo de 2016. (indefinido)

Enlaces

Ilya I. Kolykhmatov, Anton V. Yakovlev El problema del corte mínimo