A GPU based local search algorithm for the unweighted and weighted maximum s-plex problems

Given a graph G(V, E) and a value \(s \in {\mathbb {N}}\), an s-plex S is a subset of V such that each vertex \(v \in S\) has at least \(|S|-s\) adjacent vertices in the subgraph induced by S. This work proposes a GPU based local search heuristic, called GPULS, for the problems of finding an s-plex of maximum cardinality and finding an s-plex of maximum weight. The proposed heuristic works well on both problems without any modification on its parameters or its code. GPULS considers two neighborhood structures, which are explored using tabu search and a first-improvement approach. We compare GPULS with the current best-performing exact methods and heuristics. The results obtained by GPULS are highly competitive, even when it runs on a CPU-only architecture. Moreover, we observed speedups of up to 16 times by running the heuristic on a hybrid CPU–GPU architecture.