Algorithme de Karger

En algorithmique des graphes, l'algorithme de Karger est un algorithme probabiliste pour le problème de la coupe minimum (MIN-CUT). C'est donc un algorithme utilisant une source d'aléas, pour produire une solution correcte avec une bonne probabilité. Le problème en question est le suivant : étant donné un graphe non orienté trouver un ensemble de sommets non trivial minimisant le nombre d'arêtes sortant de cet ensemble.

L'outil principal de l'algorithme est la contraction aléatoire d'arêtes, qui fait décroître le nombre de sommets.

Il est dû à David Karger et a été publié en 1993^[1]. Plusieurs variations ont ensuite été proposées.

L'objet du problème est un graphe non orienté, un objet mathématique qui permet par exemple de représenter des réseaux de communications. Les nœuds du réseau sont appelés les sommets et les connexions sont les arêtes. Mathématiquement, un graphe non orienté G = ( S , A ) {\displaystyle G=(S,A)} est la donnée d'un ensemble fini, noté S {\displaystyle S} (les sommets) et d'un sous-ensemble A {\displaystyle A} de S × S {\displaystyle S\times S} (les arêtes).

On parle de coupe pour désigner deux concepts proches : un ensemble C ⊂ S {\displaystyle C\subset S} représentant une partition des sommets en deux sous-ensembles non vides S = C ∪ C ¯ {\displaystyle S=C\cup {\bar {C}}} ou bien les arêtes ayant une extrémité dans chacun de ces sous-ensembles. Lorsqu'on parle du cardinal d'une coupe, on entend le nombre d'arêtes de cette coupe. Une coupe minimum dans un graphe non orienté est une coupe de cardinal minimum. Il peut exister plusieurs coupes minimums.

Le concept de coupe minimum est relié à un autre concept fondamental en théorie des graphes, la notion de flot maximum. En effet, le théorème flot-max/coupe-min établit qu'étant donné deux sommets particuliers s 1 {\displaystyle s_{1}} et s 2 {\displaystyle s_{2}} dans le graphe, le flot maximum pouvant passer par le réseau de s 1 {\displaystyle s_{1}} à s 2 {\displaystyle s_{2}} est égal au cardinal de la coupe minimum avec la contrainte que s 1 {\displaystyle s_{1}} doit être dans un sous-ensemble et s 2 {\displaystyle s_{2}} dans l'autre.

Le problème de la coupe minimum consiste, étant donné un graphe, à déterminer une coupe minimum. Ce problème peut être résolu de façon déterministe en cherchant un flot maximum entre toute paire de sommets grâce au théorème flot-max/coupe-min. Il existe de nombreux algorithmes pour cela, par exemple l'algorithme de Ford-Fulkerson ou l'algorithme de poussage/réétiquetage. L'algorithme de Karger est beaucoup plus simple^[2] mais probabiliste.

L'algorithme est basé sur une procédure de contraction d'arête. Cette procédure consiste, étant donné un graphe G {\displaystyle G} et une arête a ≜ { s 1 , s 2 } ∈ A {\displaystyle a\triangleq \{s_{1},s_{2}\}\in A} , à fusionner s 1 {\displaystyle s_{1}} et s 2 {\displaystyle s_{2}} pour former un unique sommet s 1 s 2 {\displaystyle s_{1}s_{2}} relié à la fois aux voisins de s 1 {\displaystyle s_{1}} et au voisins de s 2 {\displaystyle s_{2}} (hormis s 1 {\displaystyle s_{1}} et s 2 {\displaystyle s_{2}} ). Le graphe ainsi formé est noté G / a {\displaystyle G/a} . Cette transformation peut faire apparaître des arêtes en double si s 1 {\displaystyle s_{1}} et s 2 {\displaystyle s_{2}} 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.

Le pseudo-code est le suivant :

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

Le nombre de sommets du graphe est réduit de un à chaque étape, il y a | S | {\displaystyle |S|} sommets au début, deux sommets à la fin. Il y a donc | S | − 2 {\displaystyle |S|-2} étapes, et l'algorithme termine.

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

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

P ( ⋂ i = 1 | S | − 2 E i ) ≥ 2 | S | ( | S | − 1 ) ≥ 2 | S | 2 {\displaystyle \mathbb {P} \left(\bigcap \limits _{i=1}^{|S|-2}E_{i}\right)\geq {\frac {2}{|S|(|S|-1)}}\geq {\frac {2}{|S|^{2}}}}

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

En répétant l'algorithme | S | 2 / 2 {\displaystyle |S|^{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 ( 1 − 2 | S | 2 ) | S | 2 2 {\displaystyle \left(1-{\frac {2}{|S|^{2}}}\right)^{\frac {|S|^{2}}{2}}} car les exécutions sont indépendantes. Cette quantité tend vers 1 / e {\displaystyle 1/e} quand | S | {\displaystyle |S|} tend vers l'infini.

Cette section est vide, insuffisamment détaillée ou incomplète. Votre aide est la bienvenue ! Comment faire ?

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 O ( | S | 2 ) {\displaystyle O(|S|^{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 O ( | S | 4 ) {\displaystyle O(|S|^{4})} .

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

L'algorithme de Karger a été inventé par Karger, et publié en 1993^[1]. Plusieurs variations et développements ont ensuite été proposés. Par exemple la complexité a été améliorée par Karger et Stein^[6]. Karger et Motwani ont montré que MIN-CUT était dans la classe de complexité appelée NC, en dérandomisant un autre algorithme utilisant le même principe de contraction^[7],[8].

L'algorithme de Karger est connu pour sa simplicité et est parfois utilisé pour introduire la notion d'algorithme probabiliste^[9].

• (en) David Karger, « Global Min-cuts in RNC and Other Ramifications of a Simple Mincut Algorithm », dans Proc. 4th Annual ACM-SIAM Symposium on Discrete Algorithms, 1993 (lire en ligne)

• (en) David R. Karger et Clifford Stein, « An O ∼ ( n 2 ) {\displaystyle O^{\sim }(n^{\mbox{2}})} algorithm for minimum cuts », dans STOC, 1993, p. 757-765

• (en) David R. Karger et Clifford Stein, « A new approach to the minimum cut problem », Journal of the ACM, vol. 43, n^o 4,‎ 1996, p. 601 (DOI 10.1145/234533.234534, lire en ligne)

• (en) Rajeev Motwani et Prabhakar Raghavan, Randomized Algorithms, Cambridge, New York et Melbourne, Cambridge University Press, 1995 (réimpr. 1997, 2000), 1^re éd., 476 p. (ISBN 978-0-521-47465-8, lire en ligne), chap. 1 (« Introduction »), p. 7-9

• Nicolas Schabanel, « Description de l'algorithme en vidéo », sur Université Paris Diderot, 2012.
• (en) Eric Vigoda, « Notes de cours sur l'algorithme de Karger », sur Georgia Institute of Technology, 2010
• (en) Sanjeev Arora, « Notes de cours », sur Université de Princeton, 2013
• (en) Sotiris Nikoletseas, « The Probabilistic Method - Randomized Algorithms (slides of lecture 1): A Monte Carlo Minimum Cut Algorithm », sur Université de Patras

• Portail de l'informatique théorique