Combinatorial algorithms for the maximum k‐plex problem

The maximum clique problem provides a classic framework for detecting cohesive subgraphs. However, this approach can fail to detect much of the cohesive structure in a graph. To address this issue, Seidman and Foster introduced k‐plexes as a degree‐based clique relaxation. More recently, Balasundaram et al. formulated the maximum k‐plex problem as an integer program and designed a branch‐and‐cut algorithm. This paper derives a new upper bound on the cardinality of k‐plexes and adapts combinatorial clique algorithms to find maximum k‐plexes.