Maximum $k$-Plex Search: An Alternated Reduction-and-Bound Method

Shuohao Gao, Kaiqiang Yu, Shengxin Liu +1

$k$-plexes relax cliques by allowing each vertex to disconnect to at most $k$ vertices. Finding a maximum $k$-plex in a graph is a fundamental operator in graph mining and has been…