Kangyi Tian: Representative Family and Its Applications

Abstract

Since it was systematically developed for parameterized algorithms in [Fomin et al., JACM 2016], the Representative Family technique has become a powerful tool in parameterized algorithm design. In this talk, I will introduce the Representative Family technique, including its core definitions, underlying intuition, and the key ideas behind efficient computation. I will then present its application to the Kidney Exchange Problem, where Representative Family leads to a deterministic algorithm improving the running time from $O^*(14.34^t)$ to $O^*(6.855^t)$. ($t$ is the solution size.) This example illustrates how the technique can be used to speed up exponential-time dynamic programming algorithms, thereby transforming them into fixed-parameter tractable algorithms.