Algorithme de Bron-Kerbosch

En informatique, l'algorithme de Bron–Kerbosch est un algorithme d'énumération pour trouver toutes les cliques maximales d'un graphe non orienté. Autrement dit, l'algorithme liste tous les sous-ensembles de sommets dans lesquels tout couple de sommets est connecté par un lien (c'est une clique), et aucun des ensembles de sommets listés ne peut être étendu en conservant cette propriété (la clique est maximale).
L'algorithme de Bron–Kerbosch a été conçu par les scientifiques néerlandais  et Joep Kerbosch qui en ont publié la description en 1973.

Bien que d'autres algorithmes aient en théorie de meilleures complexités pour résoudre le problème de la clique maximale sur des entrées qui ont un petit nombre d'ensembles indépendants, l'algorithme de Bron–Kerbosch (et ses améliorations) se révèlent souvent plus efficaces en pratique.
C'est une des raisons qui font que cet algorithme est très populaire dans des domaines d'application tels que la chimie numérique.

Un algorithme contemporain d'Akkoyunlu peut être considéré comme identique à l'algorithme de Bron–Kerbosch, quoique formulé différemment, car il génère le même arbre de recherche.

Version sans pivot 

Dans sa forme élémentaire, l'algorithme de Bron–Kerbosch est un algorithme de retour sur trace récursif qui cherche toutes les cliques maximales dans un graphe G.
Plus précisément, étant donnés trois ensembles de sommets disjoints R, P et X, il cherche toutes les cliques maximales contenant tous les sommets de R, certains de P, mais aucun de X. Précisément :
 L'ensemble R est un sous-ensemble des sommets de la potentielle clique.
 L'ensemble P est l'ensemble des sommets candidats pour être ajoutés à la potentielle clique.
 L'ensemble X contient des sommets déjà traités ou appartenant déjà à une clique maximale.
À chaque appel de l'algorithme, P et X sont des ensembles disjoints dont l'union forme des cliques lorsqu'on les ajoute à R. Autrement dit, P ⋃ X est l'ensemble des sommets qui sont connectés à tous les éléments de R.
Quand P et X sont tous les deux vides, on ne peut plus ajouter d'éléments à R, qui est donc une clique maximale que l'algorithme retourne.

Au début, les ensembles R et X sont initialisés à l'ensemble vide alors que P est l'ensemble V des sommets du graphe. À chaque appel récursif, l'algorithme examine les sommets de P l'un après l'autre ; si P est vide, soit X est vide et R est renvoyé en tant que clique maximale, soit l'algorithme retourne sur ses traces.
Pour chaque sommet v de P, l'algorithme fait un appel récursif dans lequel v est ajouté à R, et P et X sont restreints à l'ensemble des voisins N(v) de v ; cet appel renvoie toutes les extensions de cliques de R qui contiennent v.
Puis v est déplacé de P à X pour que ce sommet ne soit plus pris en considération dans les futures cliques.

Voici le pseudo-code de l'algorithme :

 algorithme BronKerbosch1(R, P, X)
     si P et X sont vides alors
         déclarer que R est une clique maximale
     pour tout sommet v dans P faire
         BronKerbosch1(R ⋃ {v}, P ⋂ N(v), X ⋂ N(v))
         P := P \ {v}
         X := X ⋃ {v}
 
 BronKerbosch1(∅, V, ∅) //appel initial

Exemple 
Exécutons l'algorithme sur le graphe ci-contre.
 BronKerbosch1(Ø, {1,2,3,4,5,6}, Ø)
          BronKerbosch1({1}, {2,5}, Ø)
                BronKerbosch1({1,2}, {5}, Ø) 
                          BronKerbosch1({1,2,5}, Ø, Ø) : sortie {1,2,5}
                P := {5}
                X := {2}
                BronKerbosch1({1,5}, Ø, {2})
          P := {2, 3, 4, 5, 6}
          X := {1}
          BronKerbosch1({2}, {3,5}, {1})
                BronKerbosch1({2,3},  Ø,  Ø) : sortie : {2,3}
                P := {3,5}
                X := {1,2}
                BronKerbosch1({2,5},  Ø,  Ø) : sortie : {2,5}
          P := {3, 4, 5, 6}
          X := {1, 2}
          BronKerbosch1({3}, {4}, Ø)
                   BronKerbosch1({3,4}, Ø, Ø) : sortie {3,4}
          P := {4, 5, 6}
          X := {1, 2, 3}
          BronKerbosch1({4}, {5,6}, {3})
                   BronKerbosch1({4,5}, Ø, Ø) : sortie {4,5}
                   BronKerbosch1({4,6}, Ø, Ø) : sortie {4,6}
          P := {5, 6}
          X := {1, 2, 3, 4}
          BronKerbosch1({5}, Ø, {2,4})
          P := {6}
          X := {1, 2, 3, 4, 5}
          BronKerbosch1({6}, Ø, {4})

Version avec pivot 

La forme élémentaire de l'algorithme décrite ci-dessus est inefficace pour les graphes qui contiennent beaucoup de cliques non maximales car on effectue un appel récursif par clique, maximale ou non.
Pour économiser du temps, Bron et Kerbosch ont introduit une version dite avec pivot. L'objectif est que l'algorithme retourne sur traces plus rapidement lorsqu'il parcourt des branches qui ne contiennent pas de cliques maximales.

Cette version utilise un « nœud pivot » u, choisi dans P ou plus généralement dans P ⋃ X, comme remarqué dans des travaux postérieurs.
Toute clique maximale doit inclure soit u, soit un nœud non voisin de u, sans quoi la clique pourrait être agrandie en y ajoutant u.
Par conséquent, il n'est nécessaire de tester que u et l'ensemble des nœuds de P qui ne sont pas voisins de u en tant que nœud v qu'on tente d'ajouter à R à chaque appel récursif de l'algorithme.

Voici le pseudo-code correspondant :

 algorithme BronKerbosch2(R, P, X)
     si P et X sont vides alors
         déclarer que R est une clique maximale
     choisir un sommet pivot u dans P ⋃ X
     pour tout sommet v dans P \ N(u) faire
         BronKerbosch2(R ⋃ {v}, P ⋂ N(v), X ⋂ N(v))
         P := P \ {v}
         X := X ⋃ {v}

Si le pivot est choisi de manière à minimiser le nombre d'appels récursifs réalisés par l'algorithme, les économies de temps de calcul par rapport à la version sans pivot peuvent être considérables.

Version avec ordonnancement des nœuds 

Une méthode alternative pour améliorer la forme élémentaire de l'algorithme de Bron–Kerbosch consiste à renoncer au pivot dans le niveau externe de la récursion, et choisir à la place d'ordonner les appels récursifs de manière à minimiser la taille des ensembles  de sommets candidats dans chaque appel récursif.

La dégénérescence d'un graphe  est le plus petit entier  tel que tout sous-graphe de  a un sommet de degré  ou moins.
Tout graphe de dégénérescence  admet un ordre tel que chaque sommet a  voisins ou moins situés après dans l'ordre.
Un tel ordre, dit ordre de dégénérescence peut être trouvé en  temps linéaire en sélectionnant itérativement le sommet de degré minimum parmi les sommets restants.
Si l'algorithme de Bron–Kerbosch visite les sommets dans un ordre de dégénérescence, alors on peut garantir que l'ensemble  des sommets candidats à chaque appel (les voisins de  qui sont situés après dans l'ordre) est au plus de taille .
L'ensemble  des sommets exclus est constitué de tous les voisins de  qui sont situés avant dans l'ordre et peut être bien plus grand que .
En-dehors du niveau le plus élevé de la récursion, la version avec pivot vue précédemment peut être utilisée.

Voici le pseudo-code correspondant : 

 algorithme BronKerbosch3(G)
     P = V(G)
     R = Ø
     X = Ø
     pour tout sommet v visités dans un ordre de dégénérescence de G faire
         BronKerbosch2({v}, P ⋂ N(v), X ⋂ N(v))
         P := P \ {v}
         X := X ⋃ {v}

On peut montrer que cette variante de l'algorithme est plus efficace pour les graphes de faible dégénérescence et des expériences montrent que l'algorithme est efficace en pratique pour les grands graphes peu denses issus de données réelles, tels que les graphes de réseaux sociaux
.

Exemple 

Dans le graphe représenté, l'algorithme est appelé initialement avec R = Ø, P = {1,2,3,4,5,6}, et X = Ø.
Le pivot u devrait être choisi parmi les nœuds de degré 3, pour minimiser le nombre d'appels récursifs. Supposons qu'on choisisse u comme étant le nœud 2, alors il reste 3 sommets dans P \ N(u): les nœuds  2 lui-même, 4 et 6.

L'itération de la boucle interne de l'algorithme pour v = 2 réalise un appel récursif avec R = {2}, P = {1,3,5} et X = Ø.
Dans cet appel récursif, soit 1 soit 5 sera choisi comme pivot, et il y aura deux appels récursifs de second niveau, un pour le nœud 3 et un autre pour le nœud qui n'a pas été choisi comme pivot.
Ces deux appels vont déclarer {1,2,5} et {2,3} comme cliques maximales.
Après le retour de ces appels récursifs, 2 est ajouté à X et retiré de P.

L'itération de la boucle interne de l'algorithme pour v = 4 réalise un appel récursif avec R = {4}, P = {3,5,6} et X = Ø (on note que 2 appartient à X pour l'appel externe de l'algorithme, mais ce n'est pas un voisin de v et est exclu du sous-ensemble X passé en argument à l'appel récursif).
Dans cet appel récursif, il y aura trois appels récursifs de second niveau, qui déclareront les cliques maximales {3,4}, {4,5} et {4,6}.
Après le retour de ces appels récursifs, 4 est ajouté à X et retiré de P.

L'itération finale de la boucle interne de l'algorithme pour v = 6 réalise un appel récursif avec R = {6}, P = Ø et X = {4}.
Comme cet appel récursif appelle sur des arguments P vide et X non-vide, il retourne immédiatement sur traces sans reporter de cliques maximales supplémentaires, puisqu'aucune clique maximale peut inclure le nœud 6 et exclure le nœud 4.

L'arbre des appels pour l'algorithme est alors :

 BronKerbosch2(Ø, {1,2,3,4,5,6}, Ø)
     BronKerbosch2({2}, {1,3,5}, Ø)
         BronKerbosch2({2,3}, Ø, Ø): sortie {2, 3}
         BronKerbosch2({2,5}, {1}, Ø)
             BronKerbosch2({1,2,5}, Ø, Ø): sortie {1,2,5}
     BronKerbosch2({4}, {3,5,6}, Ø)
         BronKerbosch2({3,4}, Ø, Ø): sortie {3,4}
         BronKerbosch2({4,5}, Ø, Ø): sortie {4,5}
         BronKerbosch2({4,6}, Ø, Ø): sortie {4,6}
     BronKerbosch2({6}, Ø, {4}): pas de sortie

Le graphe de l'exemple a une dégénérescence de deux, un ordre de dégénérescence possible est 6,4,3,1,2,5.
Avec un tel ordre sur les nœuds, la trace des appels pour la version correspondante de l'algorithme de Bron–Kerbosch est :

 BronKerbosch3(G)
     BronKerbosch2({6}, {4}, Ø)
         BronKerbosch2({6,4}, Ø, Ø): sortie {6,4}
     BronKerbosch2({4}, {3,5}, {6})
         BronKerbosch2({4,3}, Ø, Ø): sortie {4,3}
         BronKerbosch2({4,5}, Ø, Ø): sortie {4,5}
     BronKerbosch2({3}, {2}, {4})
         BronKerbosch2({3,2}, Ø, Ø): sortie {3,2}
     BronKerbosch2({1}, {2,5}, Ø)
         BronKerbosch2({1,2}, {5}, Ø)
             BronKerbosch2({1,2,5}, Ø, Ø): sortie {1,2,5}
     BronKerbosch2({2}, {5}, {1,3}): pas de sortie
     BronKerbosch2({5}, Ø, {1,2,4}): pas de sortie

Analyse dans le pire cas 

L'algorithme de Bron–Kerbosch n'est pas sensible à la taille de la sortie et contrairement à d'autres algorithmes pour résoudre le problème de la clique, sa complexité n'est pas en temps polynomial par clique maximale générée.
Cependant, d'après un résultat issu de , il est efficace dans le pire cas, dans le sens où tout graphe à n nœuds contient au plus 3n/3 cliques maximales et la complexité pire cas de l'algorithme de Bron–Kerbosch avec la stratégie du pivot qui minimise le nombre d'appels récursifs réalisés à chaque étape est en O(3n/3), atteignant donc la borne.

Pour les graphes peu denses, des bornes plus serrées sont possibles.
En particulier, dans la version de Bron–Kerbosch utilisant l'ordre de dégénérescence, l'algorithme peut être réalisé en , où  est la dégénérescence du graphe, que l'on peut comprendre comme une mesure de sa densité.
Il existe des graphes de dégénérescence  pour lesquels le nombre total de cliques maximales est , donc cette borne peut être serrée.

Notes

Références 

.
.
.
.
.
.
.
.
.
.

Liens externes 

 Review of the Bron-Kerbosch algorithm and variations par Alessio Conte.
 Bron-Kerbosh algorithm implementation in Python
 Bron-Kerbosh algorithm with vertex ordering implementation in Python
 Bron-Kerbosh algorithm implementation in C++ 
 C++ implementation of the algorithms presented in Eppstein, Strash (2011) par Darren Strash.
 Bron-Kerbosh, algorithms implementation in PHP, library with composer install par Sergio Zambrano.

Algorithmique
Théorie des graphes