A parallel exact algorithm for finding maximum cliques in undirected graphs (MaxCliquePara) has been developed. It can efficiently balance its work over multiple cores of a single computer, by traversing multiple search tree branches at the same time. The algorithm has been evaluated on DIMACS graphs and on a set of protein product graphs. The max independent set problem has also been implemented by extending the code for max clique problem.

One of the traditional ways of solving the maximum common induced subgraph problem is by reduction to a maximum clique problem. Although the maximum clique problem can be solved by a modern branch-and-bound based algorithm for general graphs, such approach is far from optimal. Some special properties of the product graph can be exploited to guide the maximum clique search. Namely, the modern state-of-the-art clique search programs use coloring as auxiliary algorithm, but finding a good coloring of a graph itself a hard task. This is supported by a published extension to the developed code. The nature of the product graph has been exploited to provide the maximum clique algorithm with a very good initial coloring or even multiple such colorings. Experiments on a large database of small to medium sized graphs have been performed and demonstrated the efficiency of the proposed method against a state of the art method for solving maximum common subgraph problem.

We are further developing this algorithm and creating a generalized C++ template system, which can be used to develop own maximum clique and related algorithms. The algorithms for finding k-cliques and all maximal cliques have already been developed using this template system.

Resources

Related projects

Graph Optimisation and Big Data
Graph Theory and Combinatorial Scientific Computing
Core research programme P2-0095

P-Lab team

Matjaž Depolli

Roman Trobec

Publications