An Exact Algorithm with New Upper Bounds for the Maximum k-Defective Clique Problem in Massive Sparse Graphs

Authors

  • Jian Gao Dalian Maritime University
  • Zhenghang Xu Jilin University
  • Ruizhi Li Jilin University of Finance and Economics
  • Minghao Yin Northeast Normal University

DOI:

https://doi.org/10.1609/aaai.v36i9.21257

Keywords:

Search And Optimization (SO)

Abstract

The Maximum k-Defective Clique Problem (MDCP), as a clique relaxation model, has been used to solve various problems. Because it is a hard computational task, previous works can hardly solve the MDCP for massive sparse graphs derived from real-world applications. In this work, we propose a novel branch-and-bound algorithm to solve the MDCP based on several new techniques. First, we propose two new upper bounds of the MDCP as well as corresponding reduction rules to remove redundant vertices and edges. The proposed reduction rules are particularly useful for massive graphs. Second, we present another new upper bound by counting missing edges between fixed vertices and an unfixed vertex for cutting branches. We perform extensive computational experiments to evaluate our algorithm. Experimental results show that our reduction rules are very effective for removing redundant vertices and edges so that graphs are reduced greatly. Also, our algorithm can solve benchmark instances efficiently, and it has significantly better performance than state-of-the-art algorithms.

Downloads

Published

2022-06-28

How to Cite

Gao, J., Xu, Z., Li, R., & Yin, M. (2022). An Exact Algorithm with New Upper Bounds for the Maximum k-Defective Clique Problem in Massive Sparse Graphs. Proceedings of the AAAI Conference on Artificial Intelligence, 36(9), 10174-10183. https://doi.org/10.1609/aaai.v36i9.21257

Issue

Section

AAAI Technical Track on Search and Optimization