El algoritmo de Bron-Kerbosh es un método de ramificación y acotación para encontrar todas las camarillas (así como los conjuntos de vértices independientes máximos ) de un gráfico no dirigido . Desarrollado por los matemáticos holandeses Bron y Kerbosch en 1973, sigue siendo uno de los algoritmos de búsqueda de camarillas más eficientes.
El algoritmo utiliza el hecho de que cada camarilla en un gráfico es su subgrafo completo de inclusión máxima . Partiendo de un solo vértice (formando un subgrafo completo), el algoritmo en cada paso intenta aumentar el subgrafo completo ya construido agregando vértices del conjunto de candidatos. Se asegura una alta velocidad cortando al iterar sobre opciones que no conducirán a la construcción de una camarilla, para lo cual se utiliza un conjunto adicional, en el que se colocan vértices que ya se han utilizado para aumentar el subgrafo completo.
El algoritmo opera en tres conjuntos de vértices de gráfico:
El algoritmo es un procedimiento recursivo aplicado a estos tres conjuntos.
PROCEDIMIENTO extender ( candidatos , no ): A MENOS QUE los candidatos estén vacíos Y no NO contenga un vértice CONECTADO A TODOS los vértices de candidatos , EJECUTAR : 1 Seleccione el vértice v de los candidatos y agréguelo a compsub 2 Forme new_candidates y new_not , eliminando de los candidatos y no los vértices no CONECTADOS a v 3 SI new_candidates y new_not están vacíos 4 TO compsub - camarilla 5 Llamada ELSE extendida recursivamente ( new_candidates , new_not ) 6 Elimine v de compsub y candidatos , y coloque notEs fácil ver que el problema de la camarilla y el problema de los conjuntos independientes son esencialmente equivalentes: cada uno de ellos se obtiene del otro construyendo un complemento gráfico , un gráfico que contiene todos los vértices del gráfico original, y en el complemento del gráfico el los vértices están conectados por una arista si y solo si no estaban conectados en el gráfico original.
Por lo tanto, el algoritmo de Bron-Kerbosch se puede usar para encontrar los conjuntos de vértices independientes de inclusión máxima mediante la construcción de una adición al gráfico original, o cambiando la condición en el bucle principal (condición de parada) y formando nuevos conjuntos new_candidates y new_not :
Lineal con respecto al número de clics en el gráfico. Tomita, Tanaka y Haruhisa en 2006 demostraron que el algoritmo del peor de los casos se ejecuta en O ( 3n /3 ), donde n es el número de vértices en el gráfico.