Algoritme de Karger

Un grafo i dos de les seues corts. La llínea punteada en roig representa un tall en tres arestes que es creuen. La llínea discontínua en vert representa un tall mínim d'este grafo, que creua solament dos arestes

En ciències de la computació i teoria de grafos, el algoritme de Karger és un procediment provabiliste per a calcular un tall mínim d'un grafo conexo. Va ser ideat per David Karger i publicat per primera volta en 1993.

L'idea de l'algoritme es basa en el concepte de contracció d'una aresta $(u,v)$ en un grafo no dirigit $G=(V,E)$. Informalmente, la contracció d'una aresta fusiona els nodos $u$ i $v$ en un, reduint el número total de nodos del grafo en un. Totes les demés arestes que conecten $u$ o $v$ es reuniran al nodo fusionat, produint efectivament un multigrafo. L'algoritme bàsic de Karger contrau iterativamente arestes elegides aleatoriamente fins que solament queden dos nodos. Estos nodos representen un talle en el grafo original. Al iterar este algoritme bàsic un número suficient de voltes, es pot trobar un tall mínim en alta provabilitat.

El problema del tall mínim global

Artícul principal → Tall mínim.

Un tall $(S,T)$ en un grafo no dirigit $G=(V,E)$ és una partició dels vèrtiços $V$ en dos conjunts no buits i disjuntos $S\cup T=V$. El conjunt de corts d'un tall consistix en les arestes $\{uv\in E:u\in S,v\in T\}$ entre les dos parts. El tamany (o pes) d'un tall en un grafo no ponderat és la cardinalidad del conjunt de corts, és dir, el número d'arestes entre les dos parts.

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

Existixen $2^{|V|}$ maneres per a determinar si cada vèrtiç pertany a $S$ o a $T$, pero dos d'estes opcions fan que $S$ o $T$ siguen interseccions buides i no generen corts. Entre les opcions restants, intercanviar els rols de $S$ i $T$ no altera el tall, per lo que cada cort es conta dos voltes; per lo tant, hi ha $2^{|V|-1}-1$ corts distints. El problema del tall mínim consistix en trobar el tall de menor tamany entre estos corts.

Per a grafos ponderats en pesos d'aresta positius $w:E\to {𝐑}^{+}$, el pes del tall és la suma dels pesos de les arestes entre els vèrtiços de cada part

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

lo que concorda en la definició no ponderada de $w=1$.

Un tall a voltes es denomina cort global per a distinguir-ho d'un tall $s$-$t$ per a un parell de vèrtiços donat, que té el requisit adicional de que $s\in S$ i $t\in T$. Tot cort global és un tall $s$-$t$ per a algun $s,t\in V$. Per lo tant, el problema del tall mínim es pot resoldre en temps polinòmic iterando sobre totes les opcions de $s,t\in V$ i resolent el problema de tall mínim resultant $s$-$t$ utilisant el teorema de fluix màxim i tall mínim i un algoritme de temps polinòmic per al fluix màxim, com l'algoritme d'inserció i reetiquetado, encara que este enfocament no és òptim. Entre els millors algoritmes determinista per al problema de tall mínim global es troba l'algoritme de Stoer-Wagner, el temps del qual d'eixecució és $O(mn+n^2\log n)$.

Algoritme de contracció

L'operació fonamental de l'algoritme de Karger és una variant de la contracció d'arestes. El resultat de contraure l'aresta $e=\{u,v\}$ és un nou nodo $uv$. Cada aresta $\{w,u\}$ o $\{w,v\}$ per a $w\notin \{u,v\}$ fins als extrems de l'aresta contreta es reemplaça per una aresta $\{w,uv\}$ fins al nou nodo. Finalment, s'eliminen els nodos contrets $u$ i $v$ en totes les seues arestes incidents. En particular, el grafo resultant no conté bucles propis. El resultat de contraure l'aresta $e$ es denota com $G/e$.

L'algoritme de contracció contrau repetidament arestes aleatòries en el grafo fins que solament queden dos nodos, moment en el qual solament hi ha un tall.

L'idea clau de l'algoritme és que és molt més provable que les arestes que no són de tall mínim se seleccionen aleatoriamente i es perguen per contracció, ya que les arestes en tall mínim solen ser àmpliament superades en número per les arestes que no són de tall mínim. Posteriorment, és plausible que les arestes en tall mínim sobrevixquen a tota la contracció d'arestes, i l'algoritme identificarà correctament l'aresta en tall mínim.

Eixecució exitosa de l'algoritme de Karger en un grafo de 10 vèrtiços. El tall mínim té un tamany de 3

   procediment contraure($G=(V,E)$):
   mentres $|V|>2$
        elegir $e\in E$ uniformemente a l'encert
        $G\leftarrow G/e$
   tornar l'únic tall en $G$

Quan el grafo es representa utilisant una llista de adyacencia o una matriu de adyacencia, es pot utilisar una sola operació de contracció d'arestes en un número llineal d'actualisacions a l'estructura de senyes, per a un temps d'eixecució total de $O(|V{|}^2)$. Alternativament, el procediment pot considerar-se com una eixecució del algoritme de Kruskal per a construir l'arbre recubridor mínim en un grafo a on les arestes tenen pesos $w(e_i)=\pi (i)$ segons una permutació aleatòria $\pi$. Eliminar l'aresta més pesada d'este arbre dona com a resultat dos components que descriuen un tall. D'esta manera, el procediment de contracció es pot dispondre com l'algoritme de Kruskal en el temps $O(|E|\log |E|)$.

Les eleccions aleatòries d'arestes en l'algoritme de Karger corresponen a una eixecució de l'algoritme de Kruskal en un gràfic en rancs d'arestes aleatoris fins que solament queden dos components

Els desenrolls més coneguts utilisen $O(|E|)$ temps i espai de memòria, o $O(|E|\log |E|)$ temps i $O(|V|)$ espai, respectivament.

Provabilitat d'èxit de l'algoritme de contracció

En un grafo $G=(V,E)$ en $n=|V|$ vèrtiços, l'algoritme de contracció torna un tall mínim en una provabilitat polinómicomente menuda, ${(\genfrac{}{}{0ex}{}{n}{2})}^{-1}$. Deu recordar-se que tot grafo té $2^{n-1}-1$ corts (segons lo explicat en la secció anterior), entre els quals $(\genfrac{}{}{0ex}{}{n}{2})$ poden ser, com a màxim, corts mínims. Per lo tant, la provabilitat d'èxit d'este algoritme és molt millor que la provabilitat d'elegir un tall a l'encert, que és, com a màxim, $\frac{(\genfrac{}{}{0ex}{}{n}{2})}{2^{n-1}-1}$.

Per eixemple, un grafo cicle en $n$ vèrtiços té exactament $(\genfrac{}{}{0ex}{}{n}{2})$ corts mínims, donats per cada elecció de 2 arestes. El procediment de contracció troba cada u d'estos en la mateixa provabilitat.

Per a establir en major precisió el llímit inferior de la provabilitat d'èxit, siga $C$ el conjunt de les arestes en un tall mínim específic de tamany $k$. L'algoritme de contracció torna $C$ si cap de les arestes aleatòries eliminades per l'algoritme pertany al conjunt de corts $C$. En particular, la primera contracció d'aresta evita $C$, lo que ocorre en una provabilitat de $1-k/|E|$. El grau mínim de $G$ és a lo manco $k$ (de lo contrari, un vèrtiç de grau mínim induiria un tall més chicotet a on una de les dos particions conté solament el vèrtiç de grau mínim), per lo que $|E|⩾nk/2$. Per lo tant, la provabilitat de que l'algoritme de contracció elegixca una aresta de $C$ és:

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

La provabilitat $p_n$ de que l'algoritme de contracció en un grafo de $n$-vèrtiços evite $C$ satisfà la recurrencia $p_n⩾(1-\frac{2}{n})p_{n-1}$, en $p_2=1$, que pot expandir-se com:

$p_n⩾\prod _{i=0}^{n-3}(1-\frac{2}{n-i})=\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}={(\genfrac{}{}{0ex}{}{n}{2})}^{-1}.$

Repetició de l'algoritme de contracció

10 repeticions del procediment de contracció. La quinta repetició determina el tall mínim de valor 3

En repetir l'algoritme de contracció $T=(\genfrac{}{}{0ex}{}{n}{2})\ln n$ voltes en eleccions aleatòries independents i obtindre el tall més menut, la provabilitat de no trobar un tall mínim és:

${[1-{(\genfrac{}{}{0ex}{}{n}{2})}^{-1}]}^T\le \frac{1}{e^{\ln n}}=\frac{1}{n}.$

El temps total d'eixecució per a $T$ repeticions per a un grafo en $n$ vèrtiços i $m$ arestes és $O(Tm)=O(n^{2}m\log n)$.