En informática , el algoritmo de Bron-Kerbosch es un algoritmo de enumeración para encontrar todas las camarillas máximas en un gráfico 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 un borde, y a ningún subconjunto enumerado se le pueden agregar vértices adicionales mientras se preserva su conectividad completa . El algoritmo 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 son, en teoría, mejores en entradas que tienen pocos conjuntos independientes máximos, con frecuencia se informa que el algoritmo de Bron-Kerbosch y sus mejoras posteriores son más eficientes en la práctica que las alternativas. [1] Es bien conocido y ampliamente utilizado en áreas de aplicación de algoritmos gráficos como la química computacional . [2]
Un algoritmo contemporáneo de Akkoyunlu (1973), aunque presentado en términos diferentes, puede considerarse igual que el 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 todas las camarillas máximas en un gráfico dado G. De manera más general, dados tres conjuntos disjuntos de vértices R , P y X , encuentra las camarillas máximas 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 consta de aquellos vértices que forman camarillas cuando se suman a R. En otras palabras, P ∪ X es el conjunto de vértices que están unidos a cada elemento de R . Cuando P y X están vacíos, no hay más elementos que puedan agregarse a R , por lo que R es una camarilla máxima y el algoritmo genera R.
La recursividad se inicia estableciendo R y X como el conjunto vacío y P como el conjunto de vértices del gráfico. Dentro de cada llamada recursiva, el algoritmo considera los vértices en P por turno; si no existen tales vértices, informa R como una camarilla máxima (si X está vacío) o retrocede. Para cada vértice v elegido de P , realiza una llamada recursiva en la que v se agrega a R y en la que P y X están restringidos al conjunto vecino N(v) de v , que encuentra e informa todas las extensiones de camarilla de R que contienen v . Luego, mueve v de P a X para excluirlo de la consideración en camarillas futuras 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 que si P y X están vacíos, entonces informe R como una camarilla máxima para cada vértice v en P. 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 gráficos con muchas camarillas no máximas: realiza una llamada recursiva para cada camarilla, máxima o no. Para ahorrar tiempo y permitir que el algoritmo retroceda más rápidamente en ramas de la búsqueda que no contienen camarillas máximas, Bron y Kerbosch introdujeron una variante del algoritmo que involucra un "vértice pivote" u , elegido entre P (o más generalmente, como investigadores posteriores realizado, [4] de P ⋃ X ). Entonces, los vecinos de ese elemento pivote no se prueban de forma recursiva. Cualquier camarilla máxima potencialmente encontrada 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 ellos siempre será parte de esa camarilla máxima. De lo contrario, sólo los vecinos de u serían parte de esa camarilla máxima, lo que permitiría aumentarla añadiéndole u , lo que contradice que esa camarilla sea máxima. Por lo tanto, sólo 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 que si P y X están vacíos, entonces se informa R como una camarilla máxima. elija un vértice pivote u en P ⋃ X para cada vértice v en P \ N( u ) do BronKerbosch2( R ⋃ { v }, P ⋂ N( v ), X ⋂ N( v )) P := P \ { v } X := X ⋃ { v }Si se elige el pivote para minimizar el número de llamadas recursivas realizadas por el algoritmo, el ahorro en tiempo de ejecución en comparación con la versión no pivotante del algoritmo puede ser significativo. [5]
Un método alternativo para mejorar la forma básica del algoritmo de Bron-Kerbosch implica renunciar al pivote en el nivel más externo de recursividad 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 recursivo. llamar.
La degeneración de un gráfico G es el número más pequeño d tal que cada subgrafo de G tiene un vértice con grado d o menos. Cada gráfico 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 adelante en el orden; Se puede encontrar un orden de degeneración 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 que recorre 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 adelante en el orden) tendrá un tamaño como máximo d . El conjunto X de vértices excluidos estará formado por 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 recursividad, aún se puede utilizar la versión pivotante. [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 do BronKerbosch2({ v }, P ⋂ N( v ), X ⋂ N( v )) P : = P \ { v } X := X ⋃ { v }Se puede demostrar 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 redes sociales grandes y 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 el número de llamadas recursivas; por ejemplo, supongamos que se elige u como vértice 2. Entonces quedan tres vértices restantes 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 cualquier vértice que no se haya elegido como pivote. Estas dos llamadas eventualmente informarán sobre 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 está excluido del subconjunto de X pasado a la llamada recursiva). Esta llamada recursiva terminará realizando tres llamadas recursivas de segundo nivel al algoritmo que informa 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 tanto, el árbol de llamadas del algoritmo tiene el siguiente aspecto:
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 posible orden de degeneración es 6,4,3,1,2,5. Si la versión de ordenación de vértices del algoritmo Bron-Kerbosch se aplica 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 Bron-Kerbosch no es un algoritmo sensible a la salida : a diferencia de otros algoritmos para el problema de camarilla, no se ejecuta en tiempo polinómico por camarilla máxima generada. Sin embargo, es eficiente en el peor de los casos: según un resultado de Moon y Moser (1965), cualquier gráfico 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 Bron-Kerbosch El algoritmo (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 gráficos dispersos , son posibles límites más estrictos. En particular, se puede hacer que la versión de ordenación de vértices del algoritmo Bron-Kerbosch se ejecute en el tiempo O( dn 3 d /3 ) , donde d es la degeneración del gráfico, una medida de su escasez. Existen d -gráficos 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 ajustado. [6]