Algorithme de Karger - Karger's algorithm

Un graphique et deux de ses coupes. La ligne pointillée en rouge est une coupe à trois bords croisés. La ligne pointillée en vert est une coupe minimale de ce graphique, ne croisant que deux arêtes.

En informatique et en théorie des graphes , l'algorithme de Karger est un algorithme aléatoire pour calculer une coupe minimale d'un graphe connecté . Il a été inventé par David Karger et publié pour la première fois en 1993.

L'idée de l'algorithme est basée sur le concept de contraction d'une arête dans un graphe non orienté . De manière informelle, la contraction d'une arête fusionne les nœuds et en un seul, réduisant le nombre total de nœuds du graphe de un. Toutes les autres arêtes se connectant soit ou sont "rattachées" au nœud fusionné, produisant effectivement un multigraphe . L'algorithme de base de Karger contracte de manière itérative les arêtes choisies au hasard jusqu'à ce qu'il ne reste plus que deux nœuds ; ces nœuds représentent une coupure dans le graphe d'origine. En itérant cet algorithme de base un nombre suffisant de fois, une coupe minimale peut être trouvée avec une probabilité élevée . ${\style d'affichage (u,v)}$${\style d'affichage G=(V,E)}$${\mode d'affichage u}$${\style d'affichage v}$${\mode d'affichage u}$${\style d'affichage v}$

Le problème de la coupe minimale globale

Une coupure dans un graphe non orienté est une partition des sommets en deux ensembles disjoints non vides . Le cutset d'une coupe se compose des bords entre les deux parties. La taille (ou poids ) d'une coupe dans un graphe non pondéré est la cardinalité de la coupe, c'est-à-dire le nombre d'arêtes entre les deux parties, ${\style d'affichage (S,T)}$${\style d'affichage G=(V,E)}$${\style d'affichage V}$${\displaystyle S\cup T=V}$${\displaystyle \{\,uv\in E\colon u\in S,v\in T\,\}}$

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

Il existe des manières de choisir pour chaque sommet s'il appartient à ou à , mais deux de ces choix font ou vident et ne donnent pas lieu à des coupures. Parmi les choix restants, permuter les rôles de et ne change pas la coupe, donc chaque coupe est comptée deux fois ; par conséquent, il y a des coupes distinctes. Le problème de la coupe minimale est de trouver une coupe de plus petite taille parmi ces coupes. ${\style d'affichage 2^{|V|}}$${\style d'affichage S}$${\style d'affichage T}$${\style d'affichage S}$${\style d'affichage T}$${\style d'affichage S}$${\style d'affichage T}$${\style d'affichage 2^{|V|-1}-1}$

Pour les graphiques pondérés avec des poids d'arête positifs, le poids de la coupe est la somme des poids des arêtes entre les sommets dans chaque partie ${\displaystyle w\colon E\rightarrow \mathbf {R} ^{+}}$

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

ce qui est conforme à la définition non pondérée de . ${\style d'affichage w=1}$

Une coupe est parfois appelée une « coupe globale » pour la distinguer d'une « coupe - » pour une paire de sommets donnée, qui a l'exigence supplémentaire que et . Chaque coupe mondiale est un - coupe pour certains . Ainsi, le problème de la coupe minimum peut être résolu en temps polynomial par itérer sur tous les choix de et résoudre le minimum résultant - problème de coupe à l' aide du théorème min-cut max-débit et un algorithme polynomial pour un débit maximal , tel que le push-relabel algorithme , bien que cette approche ne soit pas optimale. De meilleurs algorithmes déterministes pour le problème de coupe minimale globale incluent l' algorithme de Stoer-Wagner , qui a un temps d'exécution de . ${\style d'affichage s}$${\style d'affichage t}$${\displaystyle s\in S}$${\style d'affichage t\in T}$${\style d'affichage s}$${\style d'affichage t}$${\displaystyle s,t\in V}$${\displaystyle s,t\in V}$${\style d'affichage s}$${\style d'affichage t}$${\displaystyle O(mn+n^{2}\log n)}$

Algorithme de contraction

L'opération fondamentale de l'algorithme de Karger est une forme de contraction des bords . Le résultat de la contraction du bord est un nouveau nœud . Chaque arête ou pour les extrémités de l'arête contractée est remplacée par une arête vers le nouveau nœud. Enfin, les nœuds contractés et avec tous leurs bords incidents sont supprimés. En particulier, le graphe résultant ne contient pas d'auto-boucles. Le résultat de la contraction du bord est noté . ${\displaystyle e=\{u,v\}}$${\displaystyle uv}$${\displaystyle \{w,u\}}$${\style d'affichage \{w,v\}}$${\displaystyle w\notin \{u,v\}}$${\displaystyle \{w,uv\}}$${\mode d'affichage u}$${\style d'affichage v}$${\style d'affichage e}$${\displaystyle G/e}$

L'algorithme de contraction contracte à plusieurs reprises des arêtes aléatoires dans le graphe, jusqu'à ce qu'il ne reste plus que deux nœuds, auquel cas il n'y a qu'une seule coupe.

L'idée clé de l'algorithme est qu'il est beaucoup plus probable que les bords non coupés au minimum que les bords coupés au minimum soient sélectionnés au hasard et perdus par contraction, car les bords coupés au minimum sont généralement largement surpassés en nombre par les bords non coupés au minimum. Par la suite, il est plausible que les bords min-cut survivent à toute la contraction des bords, et l'algorithme identifiera correctement le bord min-cut.

Exécution réussie de l'algorithme de Karger sur un graphe à 10 sommets. La coupe minimale a la taille 3.

   procedure contract(${\displaystyle G=(V,E)}$):
   while ${\displaystyle |V|>2}$
       choose ${\displaystyle e\in E}$ uniformly at random
       ${\displaystyle G\leftarrow G/e}$
   return the only cut in ${\displaystyle G}$

Lorsque le graphique est représenté à l'aide de listes d'adjacence ou d'une matrice d'adjacence , une opération de contraction de bord unique peut être implémentée avec un nombre linéaire de mises à jour de la structure de données, pour un temps d'exécution total de . Alternativement, la procédure peut être considérée comme une exécution de l'algorithme de Kruskal pour construire l' arbre couvrant minimum dans un graphique où les arêtes ont des poids selon une permutation aléatoire . La suppression du bord le plus lourd de cet arbre entraîne deux composants qui décrivent une coupe. De cette façon, la procédure de contraction peut être implémentée comme l'algorithme de Kruskal en temps . ${\style d'affichage O(|V|^{2})}$${\style d'affichage w(e_{i})=\pi (i)}$${\style d'affichage \pi }$${\style d'affichage O(|E|\log |E|)}$

Les choix d'arêtes aléatoires dans l'algorithme de Karger correspondent à une exécution de l'algorithme de Kruskal sur un graphe avec des rangs d'arêtes aléatoires jusqu'à ce qu'il ne reste que deux composants.

Les implémentations les plus connues utilisent respectivement le temps et l'espace, ou le temps et l' espace. ${\style d'affichage O(|E|)}$${\style d'affichage O(|E|\log |E|)}$${\style d'affichage O(|V|)}$

Probabilité de succès de l'algorithme de contraction

Dans un graphe avec des sommets, l'algorithme de contraction renvoie une coupe minimale avec une probabilité polynomiale faible . Chaque graphique a des coupes, parmi lesquelles au plus peuvent être des coupes minimales. Par conséquent, la probabilité de succès de cet algorithme est bien meilleure que la probabilité de choisir une coupe au hasard, qui est au plus de . ${\style d'affichage G=(V,E)}$${\style d'affichage n=|V|}$${\displaystyle {\binom {n}{2}}^{-1}}$${\style d'affichage 2^{n-1}-1}$${\displaystyle {\tbinom {n}{2}}}$${\displaystyle {\tbinom {n}{2}}/(2^{n-1}-1)}$

Par exemple, le graphe de cycle sur les sommets a exactement des coupes minimales, données par chaque choix de 2 arêtes. La procédure de contraction trouve chacun d'eux avec une probabilité égale. ${\style d'affichage n}$${\displaystyle {\binom {n}{2}}}$

Pour établir davantage la limite inférieure de la probabilité de succès, notons les bords d'une coupe minimale spécifique de taille . L'algorithme de contraction retourne si aucune des arêtes aléatoires n'appartient à l'ensemble de coupe de . En particulier, la contraction du premier bord évite , ce qui arrive avec probabilité . Le degré minimum de est au moins (sinon un sommet de degré minimum induirait une coupe plus petite où l'une des deux partitions ne contient que le sommet de degré minimum), donc . Ainsi, la probabilité que l'algorithme de contraction sélectionne une arête est ${\style d'affichage C}$${\style d'affichage k}$${\style d'affichage C}$${\style d'affichage C}$${\style d'affichage C}$${\style d'affichage 1-k/|E|}$${\style d'affichage G}$${\style d'affichage k}$${\displaystyle |E|\geq nk/2}$${\style d'affichage C}$

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

La probabilité que l'algorithme de contraction sur un graphe à sommets évite satisfait la récurrence , avec , qui peut être développée comme ${\style d'affichage p_{n}}$${\style d'affichage n}$${\style d'affichage C}$${\displaystyle p_{n}\geq \left(1-{\frac {2}{n}}\right)p_{n-1}}$${\style d'affichage p_{2}=1}$

${\displaystyle p_{n}\geq \prod _{i=0}^{n-3}{\Bigl (}1-{\frac {2}{ni}}{\Bigr )}=\prod _{ i=0}^{n-3}{\frac {ni-2}{ni}}={\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}\,.}$

Répéter l'algorithme de contraction

10 répétitions de la procédure de contraction. La 5ème répétition trouve la coupe minimale de la taille 3.

En répétant les temps de l' algorithme de contraction avec des choix aléatoires indépendants et en retournant la plus petite coupe, la probabilité de ne pas trouver de coupe minimale est ${\displaystyle T={\binom {n}{2}}\ln n}$

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

Le temps d'exécution total pour les répétitions d'un graphe avec des sommets et des arêtes est de . ${\style d'affichage T}$${\style d'affichage n}$${\style d'affichage m}$${\displaystyle O(Tm)=O(n^{2}m\log n)}$

Algorithme de Karger-Stein

Une extension de l'algorithme de Karger due à David Karger et Clifford Stein permet une amélioration d'un ordre de grandeur.

L'idée de base est d'effectuer la procédure de contraction jusqu'à ce que le graphe atteigne les sommets. ${\style d'affichage t}$

   procedure contract(${\displaystyle G=(V,E)}$, ${\displaystyle t}$):
   while ${\displaystyle |V|>t}$
       choose ${\displaystyle e\in E}$ uniformly at random
       ${\displaystyle G\leftarrow G/e}$
   return ${\displaystyle G}$

La probabilité que cette procédure de contraction évite une coupure spécifique dans un graphe à sommets est ${\style d'affichage p_{n,t}}$${\style d'affichage C}$${\style d'affichage n}$

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

Cette expression est approximative et devient inférieure à environ . En particulier, la probabilité qu'un bord de soit contracté augmente vers la fin. Cela motive l'idée de passer à un algorithme plus lent après un certain nombre de pas de contraction. ${\style d'affichage t^{2}/n^{2}}$${\displaystyle {\frac {1}{2}}}$${\displaystyle t=n/{\sqrt {2}}}$${\style d'affichage C}$

   procedure fastmincut(${\displaystyle G=(V,E)}$):
   if ${\displaystyle |V|\leq 6}$:
       return mincut(${\displaystyle V}$)
   else:
       ${\displaystyle t\leftarrow \lceil 1+|V|/{\sqrt {2}}\rceil }$
       ${\displaystyle G_{1}\leftarrow }$ contract(${\displaystyle G}$, ${\displaystyle t}$)
       ${\displaystyle G_{2}\leftarrow }$ contract(${\displaystyle G}$, ${\displaystyle t}$)
       return min {fastmincut(${\displaystyle G_{1}}$), fastmincut(${\displaystyle G_{2}}$)}

Une analyse

La probabilité que l'algorithme trouve un cutset spécifique est donnée par la relation de récurrence ${\style d'affichage P(n)}$${\style d'affichage C}$

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

avec solution . Le temps d'exécution de fastmincut satisfait ${\displaystyle P(n)=\Omega \left({\frac {1}{\log n}}\right)}$

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

avec solution . Pour obtenir une probabilité d'erreur , l'algorithme peut être répété plusieurs fois, pour un temps d'exécution global de . Il s'agit d'une amélioration d'un ordre de grandeur par rapport à l'algorithme original de Karger. ${\displaystyle T(n)=O(n^{2}\log n)}$${\style d'affichage O(1/n)}$${\style d'affichage O(\log n/P(n))}$${\displaystyle T(n)\cdot {\frac {\log n}{P(n)}}=O(n^{2}\log ^{3}n)}$

Amélioration liée

Pour déterminer une coupe minimale, il faut toucher chaque arête du graphique au moins une fois, c'est-à-dire le temps dans un graphique dense . L'algorithme de coupe minimale de Karger-Stein prend le temps d'exécution de , qui est très proche de celui-ci. ${\displaystyle \Thêta (n^{2})}$${\displaystyle O(n^{2}\ln ^{O(1)}n)}$

Les références