Yi Zhou: Recent advances in algorithms for k-plex problems

Abstract

In the field of graph mining, the $k$-plex is a well-known extension of the clique model. A $k$-plex is nearly a clique except that each vertex is allowed to be not adjacent to at most $k$ vertices, with $k$ being a positive integer. When $k=1$, a $k$-plex is equivalent to a clique. Fundamental problems related to the $k$-plex include how to enumerate all maximal $k$-plexes and how to find the maximum $k$-plexes in a given graph. In this talk, I will present some of our recent results on these problems from the perspective of algorithm engineering. I will also introduce how techniques in the design of exact and parameterized algorithms assist in the analysis of practical $k$-plex algorithms.