A New Upper Bound Based on Vertex Partitioning for the Maximum K-plex Problem

A New Upper Bound Based on Vertex Partitioning for the Maximum K-plex Problem

Hua Jiang, Dongming Zhu, Zhichao Xie, Shaowen Yao, Zhang-Hua Fu

Proceedings of the Thirtieth International Joint Conference on Artificial Intelligence
Main Track. Pages 1689-1696. https://doi.org/10.24963/ijcai.2021/233

Given an undirected graph, the Maximum k-plex Problem (MKP) is to find a largest induced subgraph in which each vertex has at most k−1 non-adjacent vertices. The problem arises in social network analysis and has found applications in many important areas employing graph-based data mining. Existing exact algorithms usually implement a branch-and-bound approach that requires a tight upper bound to reduce the search space. In this paper, we propose a new upper bound for MKP, which is a partitioning of the candidate vertex set with respect to the constructing solution. We implement a new branch-and-bound algorithm that employs the upper bound to reduce the number of branches. Experimental results show that the upper bound is very effective in reducing the search space. The new algorithm outperforms the state-of-the-art algorithms significantly on real-world massive graphs, DIMACS graphs and random graphs.
Keywords:
Heuristic Search and Game Playing: Combinatorial Search and Optimisation
Heuristic Search and Game Playing: Heuristic Search
Data Mining: Mining Graphs, Semi Structured Data, Complex Data