En informática , el algoritmo de Bron-Kerbosch es un algoritmo de enumeración para encontrar todos los grupos máximos en un grafo no dirigido . Es decir, enumera todos los subconjuntos de vértices con las dos propiedades de que cada par de vértices en uno de los subconjuntos enumerados está conectado por una arista, y ningún subconjunto enumerado puede tener vértices adicionales agregados mientras se preserva su conectividad completa . El algoritmo de Bron-Kerbosch fue diseñado por los científicos holandeses Coenraad Bron y Joep Kerbosch, quienes publicaron su descripción en 1973.
Aunque otros algoritmos para resolver el problema de la camarilla tienen tiempos de ejecución que, en teoría, son mejores en entradas que tienen pocos conjuntos independientes máximos, el algoritmo de Bron-Kerbosch y las mejoras posteriores a este se informan con frecuencia como más eficientes en la práctica que las alternativas. [1] Es bien conocido y ampliamente utilizado en áreas de aplicación de algoritmos de gráficos como la química computacional . [2]
Un algoritmo contemporáneo de Akkoyunlu (1973), aunque presentado en términos diferentes, puede considerarse igual al algoritmo de Bron-Kerbosch, ya que genera el mismo árbol de búsqueda. [3]
La forma básica del algoritmo de Bron-Kerbosch es un algoritmo de retroceso recursivo que busca todos los cliques máximos en un grafo dado G . De manera más general, dados tres conjuntos disjuntos de vértices R , P y X , encuentra los cliques máximos que incluyen todos los vértices en R , algunos de los vértices en P y ninguno de los vértices en X . En cada llamada al algoritmo, P y X son conjuntos disjuntos cuya unión consiste en aquellos vértices que forman cliques cuando se agregan a R . En otras palabras, P ∪ X es el conjunto de vértices que se unen a cada elemento de R . Cuando P y X están vacíos, no hay más elementos que se puedan agregar a R , por lo que R es un clique máximo y el algoritmo genera R.
La recursión se inicia estableciendo R y X como el conjunto vacío y P como el conjunto de vértices del grafo. Dentro de cada llamada recursiva, el algoritmo considera los vértices en P por turno; si no hay tales vértices, informa R como un clique maximal (si X está vacío), o retrocede. Para cada vértice v elegido de P , realiza una llamada recursiva en la que v se suma a R y en la que P y X se restringen al conjunto vecino N(v) de v , que encuentra y reporta todas las extensiones de clique de R que contienen a v . Luego, mueve v de P a X para excluirlo de la consideración en futuros cliques y continúa con el siguiente vértice en P .
Es decir, en pseudocódigo, el algoritmo realiza los siguientes pasos:
El algoritmo BronKerbosch1(R, P, X) es si P y X están ambos vacíos, entonces informa R como una camarilla máxima para cada vértice v en P, haz BronKerbosch1( R ⋃ { v }, P ⋂ N ( v ), X ⋂ N ( v )) P := P \ { v } X := X ⋃ { v }La forma básica del algoritmo, descrita anteriormente, es ineficiente en el caso de grafos con muchos cliques no maximales: realiza una llamada recursiva para cada clique, maximal o no. Para ahorrar tiempo y permitir que el algoritmo retroceda más rápidamente en ramas de la búsqueda que no contienen cliques maximales, Bron y Kerbosch introdujeron una variante del algoritmo que involucra un "vértice pivote" u , elegido de P (o más generalmente, como se dieron cuenta investigadores posteriores, [4] de P ⋃ X ). Entonces, los vecinos de ese elemento pivote no se prueban recursivamente. Cualquier clique maximal potencialmente encontrado en pruebas de vecinos de u también se encontraría al probar u o uno de sus no vecinos, ya que al menos uno de estos siempre será parte de ese clique maximal. De lo contrario, solo los vecinos de u serían parte de ese clique maximal, lo que permite que se aumente añadiéndole u , lo que contradice que ese clique sea maximal. Por lo tanto, solo es necesario probar u y sus no vecinos como opciones para el vértice v que se agrega a R en cada llamada recursiva al algoritmo. En pseudocódigo:
El algoritmo BronKerbosch2(R, P, X) es si P y X están ambos vacíos, entonces informa R como una camarilla máxima elige un vértice pivote u en P ⋃ X para cada vértice v en P \ N( u ) haz BronKerbosch2( R ⋃ { v }, P ⋂ N( v ), X ⋂ N( v )) P := P \ { v } X := X ⋃ { v }Si se elige el pivote para minimizar la cantidad de llamadas recursivas realizadas por el algoritmo, los ahorros en tiempo de ejecución en comparación con la versión sin pivote del algoritmo pueden ser significativos. [5]
Un método alternativo para mejorar la forma básica del algoritmo de Bron-Kerbosch implica renunciar al pivoteo en el nivel más externo de recursión y, en su lugar, elegir cuidadosamente el orden de las llamadas recursivas para minimizar los tamaños de los conjuntos P de vértices candidatos dentro de cada llamada recursiva.
La degeneración de un grafo G es el número más pequeño d tal que cada subgrafo de G tiene un vértice con grado d o menor. Cada grafo tiene un orden de degeneración , un orden de los vértices tal que cada vértice tiene d o menos vecinos que vienen más tarde en el orden; un orden de degeneración se puede encontrar en tiempo lineal seleccionando repetidamente el vértice de grado mínimo entre los vértices restantes. Si el orden de los vértices v por los que pasa el algoritmo de Bron-Kerbosch es un orden de degeneración, entonces se garantizará que el conjunto P de vértices candidatos en cada llamada (los vecinos de v que están más tarde en el orden) tenga un tamaño de d como máximo . El conjunto X de vértices excluidos constará de todos los vecinos anteriores de v y puede ser mucho mayor que d . En llamadas recursivas al algoritmo por debajo del nivel más alto de la recursión, aún se puede usar la versión pivote. [6] [7]
En pseudocódigo, el algoritmo realiza los siguientes pasos:
El algoritmo BronKerbosch3(G) es P = V( G ) R = X = vacío para cada vértice v en un orden de degeneración de G hace BronKerbosch2({ v }, P ⋂ N( v ), X ⋂ N( v )) P := P \ { v } X := X ⋃ { v }Se ha demostrado que esta variante del algoritmo es eficiente para gráficos de pequeña degeneración, [6] y los experimentos muestran que también funciona bien en la práctica para grandes redes sociales dispersas y otros gráficos del mundo real. [7]
En el gráfico de ejemplo que se muestra, el algoritmo se llama inicialmente con R = Ø, P = {1,2,3,4,5,6} y X = Ø. El pivote u debe elegirse como uno de los vértices de grado tres, para minimizar la cantidad de llamadas recursivas; por ejemplo, supongamos que se elige u como vértice 2. Entonces quedan tres vértices en P \ N ( u ): vértices 2, 4 y 6.
La iteración del bucle interno del algoritmo para v = 2 realiza una llamada recursiva al algoritmo con R = {2}, P = {1,3,5} y X = Ø. Dentro de esta llamada recursiva, se elegirá uno de 1 o 5 como pivote, y habrá dos llamadas recursivas de segundo nivel, una para el vértice 3 y la otra para el vértice que no se haya elegido como pivote. Estas dos llamadas eventualmente informarán las dos camarillas {1,2,5} y {2,3}. Después de regresar de estas llamadas recursivas, el vértice 2 se agrega a X y se elimina de P.
La iteración del bucle interno del algoritmo para v = 4 realiza una llamada recursiva al algoritmo con R = {4}, P = {3,5,6} y X = Ø (aunque el vértice 2 pertenece al conjunto X en la llamada externa al algoritmo, no es vecino de v y se excluye del subconjunto de X que se pasa a la llamada recursiva). Esta llamada recursiva terminará realizando tres llamadas recursivas de segundo nivel al algoritmo que informan las tres camarillas {3,4} , {4,5} y {4,6}. Luego, el vértice 4 se agrega a X y se elimina de P.
En la tercera y última iteración del bucle interno del algoritmo, para v = 6, hay una llamada recursiva al algoritmo con R = {6}, P = Ø y X = {4}. Debido a que esta llamada recursiva tiene P vacío y X no vacío, inmediatamente retrocede sin informar más camarillas, ya que no puede haber una camarilla máxima que incluya el vértice 6 y excluya el vértice 4.
Por lo tanto, el árbol de llamadas del algoritmo se ve así:
BronKerbosch2(Ø, {1,2,3,4,5,6}, Ø) BronKerbosch2({2}, {1,3,5}, Ø) BronKerbosch2({2,3}, Ø, Ø): salida {2, 3} BronKerbosch2({2,5}, {1}, Ø) BronKerbosch2({1,2,5}, Ø, Ø): salida {1,2,5} BronKerbosch2({4}, {3,5,6}, Ø) BronKerbosch2({3,4}, Ø, Ø): salida {3,4} BronKerbosch2({4,5}, Ø, Ø): salida {4,5} BronKerbosch2({4,6}, Ø, Ø): salida {4,6} BronKerbosch2({6}, Ø, {4}): sin salidaEl gráfico del ejemplo tiene degeneración dos; un orden de degeneración posible es 6,4,3,1,2,5. Si se aplica la versión de ordenación de vértices del algoritmo de Bron-Kerbosch a los vértices, en este orden, el árbol de llamadas se ve así
BronKerbosch3(G) BronKerbosch2({6}, {4}, Ø) BronKerbosch2({6,4}, Ø, Ø): salida {6,4} BronKerbosch2({4}, {3,5}, {6}) BronKerbosch2({4,3}, Ø, Ø): salida {4,3} BronKerbosch2({4,5}, Ø, Ø): salida {4,5} BronKerbosch2({3}, {2}, {4}) BronKerbosch2({3,2}, Ø, Ø): salida {3,2} BronKerbosch2({1}, {2,5}, Ø) BronKerbosch2({1,2}, {5}, Ø) BronKerbosch2({1,2,5}, Ø, Ø): salida {1,2,5} BronKerbosch2({2}, {5}, {1,3}): sin salida BronKerbosch2({5}, Ø, {1,2,4}): sin salidaEl algoritmo de Bron-Kerbosch no es un algoritmo sensible a la salida : a diferencia de otros algoritmos para el problema de las camarillas, no se ejecuta en tiempo polinomial por camarilla máxima generada. Sin embargo, es eficiente en el peor de los casos: por un resultado de Moon y Moser (1965), cualquier grafo de n vértices tiene como máximo 3 n /3 camarillas máximas, y el tiempo de ejecución en el peor de los casos del algoritmo de Bron-Kerbosch (con una estrategia de pivote que minimiza el número de llamadas recursivas realizadas en cada paso) es O(3 n /3 ), lo que coincide con este límite. [8]
Para los grafos dispersos , son posibles límites más estrictos. En particular, la versión de ordenamiento de vértices del algoritmo de Bron–Kerbosch se puede ejecutar en tiempo O( dn 3 d /3 ) , donde d es la degeneración del grafo, una medida de su escasez. Existen grafos d -degenerados para los cuales el número total de camarillas máximas es ( n − d )3 d /3 , por lo que este límite es casi estricto. [6]