Yi Zhou - Exact algorithms for k-plex problems with exponential complexity analysis

Speaker: Yi Zhou

Title:  Exact algorithms for k-plex problems with exponential complexity analysis

Room: D305

Date: 12/05/2025 14:00

Abstract:

In graph theory, a k-plex is vertex set such that each vertex in the set is allowed to be not adjacent to at most k vertices in the set, with k being a positive integer. When k=1, a k-plex is equivalent to a clique, so the k-plex is a natural extension of the basic clique model. 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 report, I will present some of our recent results on these problems from the perspective of algorithm engineering. I will also introduce how techniques from the exact and parameterized algorithms assist the analysis of practical k-plex algorithms.