Local search for the maximum k -plex problem

The maximum k-plex problem is an important, computationally complex graph based problem. In this study an effective k-plex local search (KLS) is presented for solving this problem on a wide range of graph types. KLS uses data structures suitable for the graph being analysed and has mechanisms for preventing search cycling and promoting search diversity. State of the art results were obtained on 121 dense graphs and 61 large real-life (sparse) graphs. Comparisons with three recent algorithms on the more difficult graphs show that KLS performed better or as well as in 93% of 332 significant k-plex problem instances investigated achieving either larger average k-plex sizes (including some new results) or, when these were equivalent, lower CPU requirements.