Faster Computation of Representative Families for Uniform Matroids with Applications.
Hadas Shachnai, Meirav Zehavi · arXiv (Cornell University) · 2014
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. In this paper, we present a fast computation of representative families for uniform matroids. We use our computation to develop deterministic algorithms that solve k-Partial Cover and k-Internal Out-Branching in times O∗(2.619k) and O∗(6.855k), respec-tively. We thus significantly improve the best known randomized algo-rithm for k-Partial Cover and deterministic algorithm for k-Internal Out-Branching, that run in times O∗(5.437k) and O∗(16k+o(k)), respec-tively. Finally, we improve the running times of several algorithms that rely on efficient computation of representative families. 1