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) \u3b3 08(0,1], a subset of vertices S 86V is a \u3b3-quasi-clique (\u3b3-clique) if the number of edges in the subgraph induced by S is at least equal to \u3b3|S|2. The Maximum \u3b3-Quasi-Clique Problem (MQCP) aims to find a \u3b3-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, internet 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.Peer reviewed: YesNRC publication: Ye