Регистрация / Вход
Прислать материал

Algorithm Selection for the Maximum Clique Problem

Scientific organization
Laboratory of Algorithms and Technologies for Network Analysis
Academic degree
Scientific discipline
Information technologies
Algorithm Selection for the Maximum Clique Problem
In this talk a new approach for solving the maximum clique problem is presented. For every instance the suggested approach predicts if a heuristic should be used before starting an exact algorithm and predicts the fastest algorithm from several algorithms for the maximum clique problem. Then the chosen algorithm is applied for solving the maximum clique problem in a given graph. According to the computational results the proposed approach is effective and it overcomes state-of-the-art exact algorithms.
maximum clique problem, exact algorithms, machine learning

A simple, undirected graph G = (V ,E) is defined by a set of vertices V = {v1, v2,...,vn} and a set of edges E made up of pairs of distinct vertices (E ⊆ V × V ). A clique in graph G is a complete subgraph, that is, a subgraph in which vertices are pairwise adjacent. In this work, we consider the maximum clique problem (MCP), which asks for a clique of the largest cardinality in the graph. The size of a maximum clique is called the clique number of the graph and is usually denoted as ω(G).

The MCP is a well known and deeply studied NP-hard problem in graph theory. Moreover, it has found applications in many different fields, such as data association problems in bioinformatics and computational biology [1–3], computer vision [4], and robotics [5]. Such association problems may be reduced to the MCP in a correspondence graph, which subsumes the matching criteria between the two entities involved. With the upsurge of Web technologies, cliques have also been applied to capture the structure of massive networks. For example, in social networks a clique can identify a group of cooperating agents (e.g. a terrorist cell); in the World Wide Web, cliques or quasi-cliques can help detect frequently visited pages concerning a certain topic. Clique kernels can also help to identify clusters.

In the literature, there are many different approaches to solving the MCP exactly. Most successful exact solvers belong to the family of branch-and-bound algorithms that employ approximate-colour bounds [6–12]. But theoretical analysis of these algorithms appears to be difficult. Instead of it empirical analysis of the algorithm properties is made using DIMACS benchmarks. Many papers on this topic conclude that a new algorithm is better than other algorithms, if it spends less time in total on solving benchmarks than other algorithms. However the fact that some specific algorithms turn out to show better results for some specific graphs is usually ignored.

The ideal solution for this problem is to create a kind of "oracle" algorithm that would predict how much time each of the existing algorithms would spend on solving the MCP for a given graph. After that the oracle would choose the fastest algorithm. Unfortunately there is no such thing as the ideal oracle thus in practice we can only develop a heuristic for predicting the fastest algorithm from a predifined set of exact algorithms.

This work presents an approach which is based on machine learning. It selects the fastest algorithm from the set of state-of-the-art solvers. In order to do it some features were extracted and are used for the proposed approach. The computational results show that the suggested aproach is effective.        

1. Konc J, Janezic D (2010) ProBiS algorithm for detection of structurally similar protein binding sites by local structural alignment. Bioinformatics 26:1160–1168

2. Eblen J, Phillips C, Rogers G, Langston M (2012) The maximum clique enumeration problem: algorithms, applications, and implementations. BMC Bioinforma 13:S5

3. Butenko S, Chaovalitwongse W, Pardalos P (eds) (2009) Clustering challenges in biological networks. World Scientific, Singapore

4. San Segundo P, Artieda J (2015) A novel clique formulation for the visual feature matching problem. Appl Intell 43(2):325–342

5. San Segundo P, Rodriguez-Losada D (2013) Robust global feature based data association with a sparse bit optimized maximum clique algorithm. IEEE Trans Robot 29(5):1332–1339

6. Tomita E, Seki T (2003) An efficient branch and bound algorithm
for finding a maximum clique. In: Calude C, Dinneen M, Vajnovszki V (eds) Discrete Mathematics and Theoretical Computer Science. LNCS, vol 2731, pp 278–289

7. Tomita E, Sutani Y, Higashi T, Takahashi S, Wakatsuki M (2010) A simple and faster branch-and-bound algorithm for finding a
maximum clique. LNCS 5942:191–203

8. San Segundo P, Rodriguez-Losada D, Jimenez A (2011) An exact bit-parallel algorithm for the maximum clique problem. Comput Oper Res 38:2:571–581

9. San Segundo P, Matia F, Rodriguez-Losada D, Hernando M (2013) An improved bit parallel exact maximum clique algorithm. Optim Lett 7:3:467–479

10. Li C-M, Quan Z (2010) An Efficient Branch-and-Bound Algorithm based on MaxSAT for the Maximum Clique Problem. In: Proceedings AAAI, pp 128–133

11. Li C-M, Quan Z (2010) Combining Graph Structure Exploitation and Propositional Reasoning for the Maximum Clique Problem. In: Proceedings ICTAI, pp 344–351

12. San Segundo P, Nikolaev A, Batsyn M (2015) Infra-chromatic bound for exact maximum clique search. Comput Oper Res 64:293–303