Clique relaxation problems are important extension versions of the maximum clique problem with extensive real-world applications. Although lots of studies focus on designing local search algorithms for solving these problems, almost all state-of-the-art local search algorithms adopt a common general initialization method. The general initialization method only utilizes a simple search information frequency to guide the initialization procedure, ignoring other important search information and structural information that can be leveraged to generate the initial solution.
To improve the initialization procedure of clique relaxation problems, a research team led by Minghao Yin published their new research on 15 June 2025 in Frontiers of Computer Science co-published by Higher Education Press and Springer Nature.
The team proposed a group driven initialization method. It consists of a group-based initialization method, as well as two group generation and maintenance procedures. Both of them consider the useful information of the search procedure and the structure information of a given instance to a certain extent.
In detail, vertices are divided into subgroups based on a novel local optimal matrix and the definition of modularity. Based on the group information of vertices, an initial solution is obtained based on a roulette wheel method. The proposed group driven initialization method does not impact the search procedure, thus any local search algorithm based on the general local search framework for clique relaxation problems can directly apply this proposed method. The team applied the proposed initialization method to three local search algorithms that achieve the state-of-the-art performance for k-quasi-clique and k-plex, respectively. Extensive experiments are carried out to evaluate the proposed initialization method. Results show the superiority of the proposed initialization method over the common general initialization method.
DOI: 10.1007/s11704-024-40238-8