Speaker:

Kangyi Tian (University of Electronic Science and Technology of China)

Time:

• 16:20-17:20 (Time in Beijing)
• May 15, 2026 (Friday)

Venue:

518, Research Building 4

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.