An extension of adaptive multi-start tabu search for the maximum quasi-clique problem

摘要

Given a simple undirected graph G = (V, E) and real constant (threshold) gamma is an element of (0, 1], a subset of vertices S subset of V is a -quasi-clique (-clique) if the number of edges in the subgraph induced by S is at least equal to gamma((2)vertical bar S vertical bar). The Maximum -Quasi-Clique Problem (MQCP) aims to find a -quasi-clique of maximum cardinality and it was shown to be NP-hard. The MQCP has numerous applications in several real-life networks including social, biological, transportation, interne and communication networks. This paper proposes an extension of Tabu Search approach (TSQC) for solving the maximum Quasi-Clique problem. TSQC is an extension of Adaptive Multistart Tabu Search (AMTS) method given by Wu and Hao (2013) for solving the maximum clique problem (MCP). The TSQC algorithm is evaluated on DIMACS and BHOSLIB benchmark instances of the maximum clique problem and on real-life networks and compared with the most recent exact and heuristic methods. Computational results disclose that the TSQC algorithm reaches the largest known quasi-clique in a reasonable time on the real-life networks and it outperforms the existing methods on DIMACS and BHOSLIB instances. Moreover, our proposed algorithm gives some new results with improved quality of MQCP.