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

arXiv: https://arxiv.org/abs/2306.13258 · HTML: https://mlsanity.com/paper/2306.13258/

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 5 of its 46 references that are in the map.
- First posted on arXiv 23 Jun 2023.

## Builds on (most cited first, 5 of 5)

- [Exact Algorithms for Maximum Independent Set](https://mlsanity.com/paper/1312.6260/) (2013)
- [Parallel Algorithms for Finding Large Cliques in Sparse Graphs](https://mlsanity.com/paper/2109.09663/) (2021)
- [Listing Maximal k-Plexes in Large Real-World Graphs](https://mlsanity.com/paper/2202.08737/) (2022)
- [A Parameterized Algorithm for Bounded-Degree Vertex Deletion](https://mlsanity.com/paper/1601.00163/) (2016)
- [Correlating Theory and Practice in Finding Clubs and Plexes](https://mlsanity.com/paper/2212.07533/) (2022)

## Built on by (most cited first, 2 of 2)

- [An Effective Branch-and-Bound Algorithm with New Bounding Methods for the Maximum s-Bundle Problem](https://mlsanity.com/paper/2402.03736/) (2024)
- [A Faster Branching Algorithm for the Maximum k-Defective Clique Problem](https://mlsanity.com/paper/2407.16588/) (2024)

## Abstract (arXiv)

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, gk(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 gk(G), which has a worst-case running time polynomial in the size of the input graph and exponential in gk(G). In real-world inputs, gk(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 cgk(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 cgk(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.