Relaxed Graph Color Bound for the Maximum k-plex Problem

As a relaxation of the clique, a k-plex of a graph is a vertex set that each vertex is not connected with at most k vertices of this set. Given an undirected graph, the Maximum k-plex Problem (MkP) aims to find its largest k-plex. Branch and bound algorithms are a type of well-studied and effective method for exact MkP solving, whose performance depends heavily on the quality of the upper bounds. In this paper, we investigate the relaxation properties of k-plex and propose an effective upper bound called Relaxed Graph color Bound (RGB) for the MkP. To describe and calculate RGB, we propose a new quasi-independent set structure that focuses on the number of conflict vertices. We combine RGB with two of the state-of-the-art branch and bound MkP algorithms, Maplex and KpLeX. Extensive experiments on real-world benchmarks, DIMACS benchmarks, and random graphs show the excellent performance of our proposed method over the state-of-the-art algorithms.