NukCP: An Improved Local Search Algorithm for Maximum k-Club Problem


  • Jiejiang Chen Northeast Normal University
  • Yiyuan Wang Northeast Normal University
  • Shaowei Cai Institute of Software, Chinese Academy of Sciences
  • Minghao Yin Northeast Normal University
  • Yupeng Zhou Northeast Normal University
  • Jieyu Wu Northeast Normal University



Search And Optimization (SO)


The maximum k-club problem (MkCP) is an important clique relaxation problem with wide applications. Previous MkCP algorithms only work on small-scale instances and are not applicable for large-scale instances. For solving instances with different scales, this paper develops an efficient local search algorithm named NukCP for the MkCP which mainly includes two novel ideas. First, we propose a dynamic reduction strategy, which makes a good balance between the time efficiency and the precision effectiveness of the upper bound calculation. Second, a stratified threshold configuration checking strategy is designed by giving different priorities for the neighborhood in the different levels. Experiments on a broad range of different scale instances show that NukCP significantly outperforms the state-of-the-art MkCP algorithms on most instances.




How to Cite

Chen, J., Wang, Y., Cai, S., Yin, M., Zhou, Y., & Wu, J. (2022). NukCP: An Improved Local Search Algorithm for Maximum k-Club Problem. Proceedings of the AAAI Conference on Artificial Intelligence, 36(9), 10146-10155.



AAAI Technical Track on Search and Optimization