Papers › Fast Maximum k-Plex Algorithms Parameterized by Small Degeneracy Gaps
Fast Maximum k-Plex Algorithms Parameterized by Small Degeneracy Gaps
Zhengren Wang, Yi Zhou, Chunyu Luo, Mingyu Xiao, Jin-Kao Hao
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 largest k-plex from the given graph, is an important but computationally challenging problem in applications such as graph mining and community detection. So far, there are many practical algorithms, but without providing theoretical explanations on their efficiency. We define a novel parameter of the input instance, gₖ(G), the gap between the degeneracy bound and the size of the maximum k-plex in the given graph, and present an exact algorithm parameterized by this gₖ(G), which has a worst-case running time polynomial in the size of the input graph and exponential in gₖ(G). In real-world inputs, gₖ(G) is very small, usually bounded by O(log(|V|)), indicating that the algorithm runs in polynomial time. We further extend our discussion to an even smaller parameter cgₖ(G), the gap between the community-degeneracy bound and the size of the maximum k-plex, and show that without much modification, our algorithm can also be parameterized by cgₖ(G). To verify the empirical performance of these algorithms, we carry out extensive experiments to show that these algorithms are competitive with the state-of-the-art algorithms. In particular, for large k values such as $15$ and $20$, our algorithms dominate the existing algorithms. Finally, empirical analysis is performed to illustrate the effectiveness of the parameters and other key components in the implementation.
In Syntology Open this paper in Syntology's Atlas, the map of the papers in Syntology's graph and their citations.
Code
Repository list and official/mentioned flags are the archive's, frozen 2025-07-28. Reachability, where shown, is from one Syntology probe window (2026-09-16 to 2026-09-18); repositories not probed show nothing. GitHub stars are not tracked.
Code Syntology ran Syntology
Not run by Syntology. Nothing on this page verifies that the listed code works.
Tasks
Results from the paper archive 2025-07-28
No leaderboard rows for this paper in the archive.
Report a problem or propose a change · a person checks every report against the paper or source before anything changes; decisions are listed on /corrections