# Correlating Theory and Practice in Finding Clubs and Plexes

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 14 Dec 2022.

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

- [Fast Maximum k-Plex Algorithms Parameterized by Small Degeneracy Gaps](https://mlsanity.com/paper/2306.13258/) (2023)

## Abstract (arXiv)

Finding large "cliquish" subgraphs is a classic NP-hard graph problem. In this work, we focus on finding maximum s-clubs and s-plexes, i.e., graphs of diameter s and graphs where each vertex is adjacent to all but s vertices. Preprocessing based on Turing kernelization is a standard tool to tackle these problems, especially on sparse graphs. We provide a new parameterized analysis for the Turing kernelization and demonstrate their usefulness in practice. Moreover, we provide evidence that the new theoretical bounds indeed better explain the observed running times than the existing theoretical running time bounds. To this end, we suggest a general method to compare how well theoretical running time bounds fit to measured running times.