Representative Families: A Unified Tradeoff-Based Approach

Abstract

Let $M=(E,\mathcal{I})$ be a matroid, and let $\mathcal{S}$ be a family of subsets of size $p$ of $E$. A subfamily $\hat{\mathcal{S}}\subseteq \mathcal{S}$ represents $\mathcal{S}$ if for every pair of sets $X\in \mathcal{S}$ and $Y\subseteq E\setminus X$ such that $X\cup Y\in \mathcal{I}$, there is a set $\hat{X}\in \hat{\mathcal{S}}$ disjoint from $Y$ such that $\hat{X}\cup Y\in \mathcal{I}$. Fomin et al. (Proc. ACM-SIAM Symposium 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 substantially 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 approach exploits an interesting tradeoff between running time and the size of the representative families.