Efficient Computation of Representative Families with Applications in Parameterized and Exact Algorithms

Abstract

Let M=(E, I) be a matroid and let S={S1, ċ , St} be a family of subsets of E of size p. A subfamily Ŝ ⊆ S is q-representative for S if for every set Y⊆E of size at most q, if there is a set X ∈ S disjoint from Y with X∪ Y ∈ I, then there is a set Xˆ ∈ Ŝ disjoint from Y with Xˆ ∪ Y ∈ I. By the classic result of Bollobás, in a uniform matroid, every family of sets of size p has a q-representative family with at most (p+qp) sets. In his famous “two families theorem” from 1977, Lovász proved that the same bound also holds for any matroid representable over a field F. We give an efficient construction of a q-representative family of size at most (p+qp) in time bounded by a polynomial in (p+qp), t, and the time required for field operations.