Fast Maximum $k$-Plex Algorithms Parameterized by Small Degeneracy Gaps

Zhengren Wang, Yi Zhou, Chunyu Luo +2

Given a graph, a $k$-plex is a set of vertices in which each vertex is not adjacent to at most $k-1$ other vertices in the set. The maximum $k$-plex problem, which asks for the lar…