Algorithme de Bron-Kerbosch

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 nœuds 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 de nœuds 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 nœud 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 retourne toutes les extensions de cliques de R qui contiennent v. Puis v est déplacé de P à X pour que ce nœud 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 R clique maximale
    pour tout sommet v de P faire
        BronKerbosch1(R ⋃ {v}, P ⋂ N(v), X ⋂ N(v))
        P := P \ {v}
        X := X ⋃ {v}

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 en permettant à l'algorithme de retourner sur traces plus rapidement lorsqu'il parcourt des branches qui ne contiennent pas de cliques maximales, Bron et Kerbosch ont introduit une variante qui utilise un « nœud pivot » u, choisi dans P ou plus généralement dans P ⋃ X, comme remarqué dans des travaux postérieurs[5]. Toute clique maximale doit inclure soit u, soit un nœud qui n'est pas parmi les voisins 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 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 R 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[6].

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 P de sommets candidats dans chaque appel récursif.

La dégénérescence d'un graphe G est le plus petit entier d tel que tout sous-graphe de G a un sommet de degré d ou moins. Tout graphe de dégénérescence d admet un ordre tel que chaque sommet a d 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 P des sommets candidats à chaque appel (les voisins de v qui sont situés après dans l'ordre) est au plus de taille d. L'ensemble X des sommets exclus est constitué de tous les voisins de v qui sont situés avant dans l'ordre et peut être bien plus grand que d. En-dehors du niveau le plus élevé de la récursion, la version avec pivot vue précédemment peut être utilisée[7] - [8].

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[7] 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[8] .

Un graphe comprenant 5 cliques maximales: 5 liens et un triangle.

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

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 Moon et Moser 1965, il est efficace dans le pire cas, dans le sens où tout graphe à n nœuds contient au plus 3^n/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(3^n/3), atteignant donc la borne[9].

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(dn3^d/3), où d 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 d pour lesquels le nombre total de cliques maximales est (n − d)3^d/3, donc cette borne peut être serrée[7].

• (en) Cet article est partiellement ou en totalité issu de l’article de Wikipédia en anglais intitulé « Bron-Kerbosch algorithm » (voir la liste des auteurs).

• 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.