Department of
Applied
Mathematics

Representative sets for multisets

Ariel Gabizon

Abstract

The notion of a q-representative set for a family of subsets, originally arising in the Two-Families Theorem of Bollobás, has recently proven to be very useful in the design of parameterized and exact algorithms.

In this talk I will explain this notion. Then, to illustrate its usefulness, I will show how it was used by Fomin, Lokshtanov and Saurabh to design a fast algorithm for finding long simple paths in a directed graph.

Finally, I will describe a recent work where we generalize the notion of a representative set to a family of multisets and derive algorithmic applications.

Based on joint work with Fedor V. Fomin, Daniel Lokshtanov and Saket Saurabh