Lecture
The Bron–Kerbosch algorithm — a branch-and-bound method for finding all cliques (and also the maximal independent vertex sets) of an undirected graph. It was developed by the Dutch mathematicians Bron and Kerbosch in 1973 and is still one of the most efficient algorithms for finding cliques.
The algorithm exploits the fact that every clique in a graph is a maximal (with respect to inclusion) complete subgraph. Starting from a single vertex (which forms a complete subgraph), at each step the algorithm tries to enlarge the complete subgraph already built by adding vertices from the candidate set. Its high speed is achieved by pruning, during the enumeration, the options that clearly cannot lead to a clique; for this purpose an additional set is used, into which the vertices that have already been used to enlarge the complete subgraph are placed.
The algorithm operates on three sets of graph vertices:
The algorithm is a recursive procedure applied to these three sets.
PROCEDURE extend (candidates, not): WHILE candidates is NOT empty AND not does NOT contain a vertex CONNECTED TO ALL vertices of candidates, DO: 1 Choose a vertex v from candidates and add it to compsub 2 Form new_candidates and new_not by removing from candidates and not the vertices NOT CONNECTED to v 3 IF new_candidates and new_not are empty 4 THEN compsub – is a clique 5 ELSE recursively call extend (new_candidates, new_not) 6 Remove v from compsub and candidates, and place it into not
It is easy to see that the clique problem and the independent-set problem are essentially equivalent: each of them is obtained from the other by constructing the complement of the graph — a graph that has all the vertices of the original graph, and in which two vertices are joined by an edge if and only if they were not joined in the original graph.
Therefore the Bron–Kerbosch algorithm can be used to find the maximal (with respect to inclusion) independent vertex sets, either by constructing the complement of the original graph, or by changing the condition in the main loop (the stopping condition) and the formation of the new sets new_candidates and new_not:
Linear in the number of cliques in the graph. Tomita, Tanaka and Haruhisa showed in 2006 that in the worst case the algorithm runs in O(3n/3), where n — is the number of vertices in the graph.
Comments