NuQClq: An Effective Local Search Algorithm for Maximum Quasi-Clique Problem
Keywords:Local Search, Heuristic Search
AbstractThe maximum quasi-clique problem (MQCP) is an important extension of maximum clique problem with wide applications. Recent heuristic MQCP algorithms can hardly solve large and hard graphs effectively. This paper develops an efficient local search algorithm named NuQClq for the MQCP, which has two main ideas. First, we propose a novel vertex selection strategy, which utilizes cumulative saturation information to be a selection criterion when the candidate vertices have equal values on the primary scoring function. Second, a variant of configuration checking named BoundedCC is designed by setting an upper bound for the threshold of forbidding strength. When the threshold value of vertex exceeds the upper bound, we reset its threshold value to increase the diversity of search process. Experiments on a broad range of classic benchmarks and sparse instances show that NuQClq significantly outperforms the state-of-the-art MQCP algorithms for most instances.
How to Cite
Chen, J., Cai, S., Pan, S., Wang, Y., Lin, Q., Zhao, M., & Yin, M. (2021). NuQClq: An Effective Local Search Algorithm for Maximum Quasi-Clique Problem. Proceedings of the AAAI Conference on Artificial Intelligence, 35(14), 12258-12266. https://doi.org/10.1609/aaai.v35i14.17455
AAAI Technical Track on Search and Optimization