Bron–Kerbosch algorithm
Algorithm for listing maximal cliques
- 8 min read
- 5 chapters
Related on Lably
Through Computer science, Graph (discrete mathematics) and Subset
Although other algorithms for solving the clique problem have running times that are, in theory, better on inputs that have few maximal independent sets, the Bron–Kerbosch algorithm and subsequent improvements to it are frequently reported as being more efficient in practice than the alternatives. It is well-known and widely used in application areas of graph algorithms such as computational chemistry.
A contemporaneous algorithm of Akkoyunlu (1973), although presented in different terms, can be viewed as being the same as the Bron–Kerbosch algorithm, as it generates the same search tree.
Without pivoting
The basic form of the Bron–Kerbosch algorithm is a recursive backtracking algorithm that searches for all maximal cliques in a given graph G. More generally, given three disjoint sets of vertices R, P, and X, it finds the maximal cliques that include all of the vertices in R, some of the vertices in P, and none of the vertices in X. In each call to the algorithm, P and X are disjoint sets whose union consists of those vertices that form cliques when added to R. In other words, P ∪ X is the set of vertices which are joined to every element of R. When P and X are both empty there are no further elements that can be added to R, so R is a maximal clique and the algorithm outputs R.
The recursion is initiated by setting R and X to be the empty set and P to be the vertex set of the graph. Within each recursive call, the algorithm considers the vertices in P in turn; if there are no such vertices, it either reports R as a maximal clique (if X is empty), or backtracks. For each vertex v chosen from P, it makes a recursive call in which v is added to R and in which P and X are restricted to the neighbor set N(v) of v, which finds and reports all clique extensions of R that contain v. Then, it moves v from P to X to exclude it from consideration in future cliques and continues with the next vertex in P.
That is, in pseudocode, the algorithm performs the following steps:
<b id="mwTg">algorithm</b> BronKerbosch1(R, P, X) <b id="mwTw">is</b> <b id="mwUA">if</b> <i id="mwUQ">P</i> <b id="mwUg">and</b> <i id="mwUw">X</i> are both empty <b id="mwVA">then</b> report <i id="mwVQ">R</i> as a maximal clique <b id="mwVg">for each</b> vertex <i id="mwVw">v</i> <b id="mwWA">in</b> <i id="mwWQ">P</i> <b id="mwWg">do</b> BronKerbosch1(<i id="mwWw">R</i> ⋃ {<i id="mwXA">v</i>}, <i id="mwXQ">P</i> ⋂ <i id="mwXg">N</i>(<i id="mwXw">v</i>), <i id="mwYA">X</i> ⋂ <i id="mwYQ">N</i>(<i id="mwYg">v</i>)) <i id="mwYw">P</i> := <i id="mwZA">P</i> \ {<i id="mwZQ">v</i>} <i id="mwZg">X</i> := <i id="mwZw">X</i> ⋃ {<i id="mwaA">v</i>}Sign in to keep reading
4 more chapters are free with a Lably account.
With pivoting
The basic form of the algorithm, described above, is inefficient in the case of graphs with many non-maximal cliques: it makes a recursive call for every clique, maximal or not. To save time and allow the algorithm to backtrack more quickly in branches of the search that contain no maximal cliques, Bron and Kerbosch introduced a variant of the algorithm involving a "pivot vertex" u, chosen from P (or more generally, as later investigators realized, from P ⋃ X). Then, neighbors of that pivot element are not recursively tested. Any maximal clique potentially found in tests of neighbors of u would also be found when testing u or one of its non-neighbors, as at least one of these will always be a part of that maximal clique. Otherwise, only neighbors of u would be part of that maximal clique, allowing it to be augmented by adding u to it, which contradicts that clique being maximal. Therefore, only u and its non-neighbors need to be tested as the choices for the vertex v that is added to R in each recursive call to the algorithm. In pseudocode:
<b id="mwfQ">algorithm</b> BronKerbosch2(R, P, X) <b id="mwfg">is</b> <b id="mwfw">if</b> <i id="mwgA">P</i> and <i id="mwgQ">X</i> are both empty <b id="mwgg">then</b> report <i id="mwgw">R</i> as a maximal clique choose a pivot vertex <i id="mwhA">u</i> in <i id="mwhQ">P</i> ⋃ <i id="mwhg">X</i> <b id="mwhw">for each</b> vertex <i id="mwiA">v</i> <b id="mwiQ">in</b> <i id="mwig">P</i> \ N(<i id="mwiw">u</i>) <b id="mwjA">do</b> BronKerbosch2(<i id="mwjQ">R</i> ⋃ {<i id="mwjg">v</i>}, <i id="mwjw">P</i> ⋂ N(<i id="mwkA">v</i>), X ⋂ N(<i id="mwkQ">v</i>)) <i id="mwkg">P</i> := <i id="mwkw">P</i> \ {<i id="mwlA">v</i>} <i id="mwlQ">X</i> := <i id="mwlg">X</i> ⋃ {<i id="mwlw">v</i>}If the pivot is chosen to minimize the number of recursive calls made by the algorithm, the savings in running time compared to the non-pivoting version of the algorithm can be significant.
With vertex ordering
An alternative method for improving the basic form of the Bron–Kerbosch algorithm involves forgoing pivoting at the outermost level of recursion, and instead choosing the ordering of the recursive calls carefully in order to minimize the sizes of the sets P of candidate vertices within each recursive call.
The degeneracy of a graph G is the smallest number d such that every subgraph of G has a vertex with degree d or less. Every graph has a degeneracy ordering, an ordering of the vertices such that each vertex has d or fewer neighbors that come later in the ordering; a degeneracy ordering may be found in linear time by repeatedly selecting the vertex of minimum degree among the remaining vertices. If the order of the vertices v that the Bron–Kerbosch algorithm loops through is a degeneracy ordering, then the set P of candidate vertices in each call (the neighbors of v that are later in the ordering) will be guaranteed to have size at most d. The set X of excluded vertices will consist of all earlier neighbors of v, and may be much larger than d. In recursive calls to the algorithm below the topmost level of the recursion, the pivoting version can still be used.
In pseudocode, the algorithm performs the following steps:
<b id="mwvw">algorithm</b> BronKerbosch3(G) <b id="mwwA">is</b> <i id="mwwQ">P</i> = V(<i id="mwwg">G</i>) <i id="mwww">R</i> = X = empty <b id="mwxA">for each</b> vertex <i id="mwxQ">v</i> in a degeneracy ordering of <i id="mwxg">G</i> <b id="mwxw">do</b> BronKerbosch2({<i id="mwyA">v</i>}, <i id="mwyQ">P</i> ⋂ N(<i id="mwyg">v</i>), X ⋂ N(<i id="mwyw">v</i>)) <i id="mwzA">P</i> := <i id="mwzQ">P</i> \ {<i id="mwzg">v</i>} <i id="mwzw">X</i> := <i id="mw0A">X</i> ⋃ {<i id="mw0Q">v</i>}This variant of the algorithm can be proven to be efficient for graphs of small degeneracy, and experiments show that it also works well in practice for large sparse social networks and other real-world graphs.
Example
In the example graph shown, the algorithm is initially called with R = Ø, P = {1,2,3,4,5,6}, and X = Ø. The pivot u should be chosen as one of the degree-three vertices, to minimize the number of recursive calls; for instance, suppose that u is chosen to be vertex 2. Then there are three remaining vertices in P \ N(u): vertices 2, 4, and 6.
The iteration of the inner loop of the algorithm for v = 2 makes a recursive call to the algorithm with R = {2}, P = {1,3,5}, and X = Ø. Within this recursive call, one of 1 or 5 will be chosen as a pivot, and there will be two second-level recursive calls, one for vertex 3 and the other for whichever vertex was not chosen as pivot. These two calls will eventually report the two cliques {1,2,5} and {2,3}. After returning from these recursive calls, vertex 2 is added to X and removed from P.
The iteration of the inner loop of the algorithm for v = 4 makes a recursive call to the algorithm with R = {4}, P = {3,5,6}, and X = Ø (although vertex 2 belongs to the set X in the outer call to the algorithm, it is not a neighbor of v and is excluded from the subset of X passed to the recursive call). This recursive call will end up making three second-level recursive calls to the algorithm that report the three cliques {3,4}, {4,5}, and {4,6}. Then, vertex 4 is added to X and removed from P.
In the third and final iteration of the inner loop of the algorithm, for v = 6, there is a recursive call to the algorithm with R = {6}, P = Ø, and X = {4}. Because this recursive call has P empty and X non-empty, it immediately backtracks without reporting any more cliques, as there can be no maximal clique that includes vertex 6 and excludes vertex 4.
The call tree for the algorithm, therefore, looks like:
BronKerbosch2(Ø, {1,2,3,4,5,6}, Ø) BronKerbosch2({2}, {1,3,5}, Ø) BronKerbosch2({2,3}, Ø, Ø): output {2, 3} BronKerbosch2({2,5}, {1}, Ø) BronKerbosch2({1,2,5}, Ø, Ø): output {1,2,5} BronKerbosch2({4}, {3,5,6}, Ø) BronKerbosch2({3,4}, Ø, Ø): output {3,4} BronKerbosch2({4,5}, Ø, Ø): output {4,5} BronKerbosch2({4,6}, Ø, Ø): output {4,6} BronKerbosch2({6}, Ø, {4}): no outputThe graph in the example has degeneracy two; one possible degeneracy ordering is 6,4,3,1,2,5. If the vertex-ordering version of the Bron–Kerbosch algorithm is applied to the vertices, in this order, the call tree looks like
BronKerbosch3(G) BronKerbosch2({6}, {4}, Ø) BronKerbosch2({6,4}, Ø, Ø): output {6,4} BronKerbosch2({4}, {3,5}, {6}) BronKerbosch2({4,3}, Ø, Ø): output {4,3} BronKerbosch2({4,5}, Ø, Ø): output {4,5} BronKerbosch2({3}, {2}, {4}) BronKerbosch2({3,2}, Ø, Ø): output {3,2} BronKerbosch2({1}, {2,5}, Ø) BronKerbosch2({1,2}, {5}, Ø) BronKerbosch2({1,2,5}, Ø, Ø): output {1,2,5} BronKerbosch2({2}, {5}, {1,3}): no output BronKerbosch2({5}, Ø, {1,2,4}): no outputWorst-case analysis
The Bron–Kerbosch algorithm is not known to be an output-sensitive algorithm: unlike some other algorithms for the clique problem, it is not known to run in polynomial time per maximal clique generated. However, it is efficient in a worst-case sense: by a result of Moon & Moser (1965), any n-vertex graph has at most 3n/3 maximal cliques, and the worst-case running time of the Bron–Kerbosch algorithm (with a pivot strategy that minimizes the number of recursive calls made at each step) is O(3n/3), matching this bound.
For sparse graphs, tighter bounds are possible. In particular the vertex-ordering version of the Bron–Kerbosch algorithm can be made to run in time O(dn3d/3), where d is the degeneracy of the graph, a measure of its sparseness. There exist d-degenerate graphs for which the total number of maximal cliques is (n − d)3d/3, so this bound is close to tight.