Maximum k-Plex Computation: Theory and Practice

The k-plex model relaxes the clique model by allowing each vertex to miss up to k neighbors, including the vertex itself. A 1-plex is a clique. Many exact algorithms have been recently designed for finding the k-plex with the largest number of vertices, known as the maximum k-plex computation problem. However, all the existing algorithms, except BS, has the trivial worst-case time complexity of O* (2n) when ignoring polynomial factors. On the other hand, although BS improves the time complexity to O* (βkn) where βk < 2 is a constant depending only on k, its practical performance is not satisfactory. In this paper, we study the maximum k-plex computation problem from both theory and practice. We first propose two new reduction rules and a new branching rule and prove that the base of the exponential time complexity is reduced to γk when the new reduction and branching rules are incorporated into a standard backtracking algorithm; here γk < βk. We then design a two-stage approach kPlexT to improve the exponent of the time complexity by separating the search of large k-plexes from the search of small ones. We prove that kPlexT runs in O* ( (α Δ) k+1 γₖα) time when the maximum k-plex size Ωk (G) is at least 2k-1, and in O* ( (α Δ) k+1 γₖα + min (γkn, n2k-2) ) time otherwise; here, α is the degeneracy and Δ is the maximum degree of the input graph. We also prove that with slight modification, kPlexT runs in O* ( (αΔ) k+1 (k+1) α+k-Ωk (G) ) time when ømegaₖ (G) ≥ 2k-1. Finally, we propose another reduction rule and a better initialization method to improve the practical performance of kPlexT. Extensive empirical studies demonstrate that kPlexT achieves state-of-the-art practical performance. We also show that our improved time complexity carries over to other related problems such as enumerating all maximal k-plexes, quasi-cliques, and k-biplexes.