Algorithme de Karger

Contraction d'une arête (en gras).

L'algorithme est basé sur une procédure de contraction d'arête. Cette procédure consiste, étant donné un graphe G et une arête e=(a,b), à fusionner a et b pour former un unique sommet ab relié à la fois aux voisins de a et au voisins de b (hormis a et b). Le graphe ainsi formé est noté G/e. Cette transformation peut faire apparaître des arêtes en double si a et b partagent un voisin. Après plusieurs contractions on a des multi-arêtes et on travaille donc avec des multigraphes. Le point important est qu'une coupe dans le graphe après contraction, était déjà une coupe dans le graphe de départ[3].

L'algorithme consiste simplement à contracter une arête tirée uniformément dans le graphe, à la contracter, et à recommencer l'opération jusqu'à n'avoir que deux sommets. Les deux sommets représentent la partition de sommets, et les arêtes entre eux deux sont les arêtes de la coupe.

Un exemple d’exécution de l'algorithme est donné par l'image suivante.

Un déroulement de l'algorithme de Karger sur un graphe.

10 répétitions de l'algorithme de Karger.

Le pseudo-code est le suivant :

   fonction contraction(G=(V,E)):
       tant que |V| > 2
           choisir e dans E aléatoirement (*fonction aléatoire uniforme*)
           G ← G/e
       retourner l'unique coupure de G

Le nombre de sommets du graphe est réduit de un à chaque étape, il y a donc n-2 étapes, et l'algorithme termine.

Soit k la taille de la coupe minimum du graphe G, et soit C une telle coupe (vue comme un ensemble d'arêtes). Remarquons que le degré minimum de G est k sinon on pourrait isoler un sommet de bas degré et obtenir une coupe de taille inférieure à k. On cherche à savoir la probabilité d'avoir C à la fin de l'algorithme, c'est-à-dire la probabilité de n'avoir contracté aucune arête de C.

En notant n le nombre de sommet et ${\displaystyle E_{i}}$ l’événement « l'arête contractée à l'étape ${\displaystyle i}$ n'appartient pas à C » , on peut montrer[4] que

${\displaystyle Pr\left(\cap _{i=1}^{n-2}E_{i}\right)\geq {\frac {2}{n(n-1)}}\geq {\frac {2}{n^{2}}}}$

Donc la probabilité de succès est au moins ${\displaystyle 2/n^{2}}$.

En répétant l'algorithme ${\displaystyle n^{2}/2}$ fois, on peut avoir un algorithme avec une probabilité de succès constante. En effet la probabilité d'échec pour l'algorithme répété est au plus ${\displaystyle \left(1-{\frac {2}{n^{2}}}\right)^{\frac {n^{2}}{2}}}$ car les exécutions sont indépendantes. Cette quantité tend vers 1/e quand n tend vers l'infini.

Pour un graphe donné sous forme de liste d'adjacence ou de matrice d'adjacence, un run de l'algorithme peut être implémenté en temps ${\displaystyle O(n^{2})}$, on a donc une complexité quadratique en fonction du nombre de nœuds. Avec un nombre quadratique de répétitions on obtient un algorithme en ${\displaystyle O(n^{4})}$.

Cette complexité peut être améliorée pour obtenir un algorithme quasi quadratique, de probabilité d'erreur tendant vers zéro avec n tendant vers l'infini[5].