An Exact Algorithm for Maximum k-Plexes in Massive Graphs

An Exact Algorithm for Maximum k-Plexes in Massive Graphs

Jian Gao, Jiejiang Chen, Minghao Yin, Rong Chen, Yiyuan Wang

Proceedings of the Twenty-Seventh International Joint Conference on Artificial Intelligence
Main track. Pages 1449-1455. https://doi.org/10.24963/ijcai.2018/201

The maximum k-plex, a generalization of maximum clique, is used to cope with a great number of real-world problems. The aim of this paper is to propose a novel exact k-plex algorithm that can deal with large-scaled graphs with millions of vertices and edges. Specifically, we first propose several new graph reduction methods through a careful analyzing of structures of induced subgraphs. Afterwards, we present a preprocessing method to simplify initial graphs. Additionally, we present a branch-and-bound algorithm integrating the reduction methods as well as a new dynamic vertex selection mechanism. We perform intensive experiments to evaluate our algorithm, and show that the proposed strategies are effective and our algorithm outperforms state-of-the-art algorithms, especially for real-world massive graphs.
Keywords:
Heuristic Search and Game Playing: Heuristic Search
Heuristic Search and Game Playing: Combinatorial Search and Optimisation