Two New Upper Bounds for the Maximum k-plex Problem

A k-plex in a graph is a vertex set where each vertex is non-adjacent to at most k vertices (including itself) in this set, and the Maximum k-plex Problem (MKP) is to find the largest k-plex in the graph. MKP is a practical NP-hard problem, and the k-plex model has many important real-world applications, such as the analysis of various complex networks. Branch-and-bound (BnB) algorithms are a type of well-studied and effective exact algorithms for MKP. Recent BnB MKP algorithms involve two kinds of upper bounds based on graph coloring and partition, respectively, that work in different perspectives and thus are complementary with each other. In this paper, we first propose a new coloring-based upper bound, termed Relaxed Graph Color Bound (RelaxGCB), that significantly improves the previous coloring-based upper bound. Then we propose another new upper bound, termed SeesawUB, inspired by the seesaw playing game, that incorporates RelaxGCB and a partition-based upper bound in a novel way, making use of their complementarity. We apply RelaxGCB and SeesawUB to state-of-the-art BnB MKP algorithms and produce four new algorithms. Extensive experiments show the excellent performance and robustness of the new algorithms with our proposed upper bounds.