Maximum Clique Algorithm

Why use it?

• A fast algorithm for finding a maximum clique in an undirected graph has been developed in our laboratory with purpose of quickly comparing large molecular structures. A clique is a fully connected subgraph of a graph and a maximum clique is the clique with the largest number of vertices in a given graph. A maximum clique in an associative graph G1 X G2 corresponds with the maximum common subgraph of the graphs G1 and G2. When comparing protein structures represented as graphs, maximum common subgraph translates to the largest similarity in topology or properties of the compared proteins.


• Maximum clique algorithms differ from maximal clique algorithms, e.g., Bron-Kerbosch algorithm. The maximal search is for all maximal cliques in a graph (cliques that cannot be enlarged), while the maximum clique algorithms find a maximum clique (a clique with the largest number of vertices). Maximum clique search is approx. an order of magnitude faster to compute. Maximum clique algorithms are preffered to maximal clique algorithms when comparing molecular structures, because knowing all (smaller) cliques is not necessary when comparing rigid 2D or 3D objects. Only the largest one is important. This algorithm is considerably faster than the algorithms of Tomita et al. (LNCS, 2003) and Oestergard (Discrete Applied Mathematics, 2002) on DIMACS and random graphs.


• The algorithm is used for comparing large protein structures (see ProBiS).

Instructions

• Compile (under Ubuntu) with: g++ -O3 maxcliquedyn.cc -o mcqd


• Running the program from shell, you have to provide the DIMACS formatted graph file and the Tlimit parameter (=0.025), e.g., $mcqd brock200_1.clq 0.025


• If the calculation of max clique takes less than ca. 1.0 sec, then this version will repeat the calculation 10 times, so that we get more reliable, average time of calculation in the end.


• The C/C++ source of the program with an example graph in DIMACS format are available (please note that vertices in the example graph are re-enumerated by the algorithm from 1,2,3,...10 to 0,1,2,...,9).

Translation of the output (it is in slovenian)

• na koraku 23336072 sem nasel qmax dolzine 41
  Stevilo korakov = 25459881 dolocanj degree-jev = 474835 obseg dolocanj = 40128070
  


• On step 23336072 the algorithm found current (not final) maximum clique of 41 vertices. One step is one visit of a search tree node.


• The total number of steps (=25459881)


• The number of steps on which a computationally intensive re-calculation of degrees and resorting of vertices in current solution (=474835) had to be performed. See also function DEGREES_SORT. Always, this value is comparably much smaller than the number of steps, because we re-sort vertices in only about 2.5% of all steps (see Tlimit parameter) !


• The sum of sizes (numbers of vertices) in all current solutions, that needed resorting (=40128070)

Citation

• KONC, Janez, JANEŽIČ, Dušanka. An improved branch and bound algorithm for the maximum clique problem. MATCH Commun. Math. Comput. Chem., 2007, 58, 569-590.