Representative Families: A Unified Tradeoff-Based Approach

Abstract. LetM=(E, I) be a matroid, and let S be a family of subsets of size p of E. A subfamily S ̂ ⊆ S represents S if for every pair of sets X ∈S and Y ⊆E\X such that X∪Y ∈ I, there is a set X ̂ ∈ S ̂ disjoint from Y such that X̂∪Y ∈ I. Fomin et al. (Proc. ACM-SIAM Sympo-sium on Discrete Algorithms, 2014) introduced a powerful technique for fast computation of representative families for uniform matroids. In this paper, we show that this technique leads to a unified approach for sub-stantially improving the running times of parameterized algorithms for some classic problems. This includes, among others, k-Partial Cover, k-Internal Out-Branching, and Long Directed Cycle. Our ap-proach exploits an interesting tradeoff between running time and the size of the representative families.