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

Let M = (E, I) be a matroid and let S = {S-1,..., S-t} be a family of subsets of E of size p. A subfamily (S) over cap subset of S is q-representative for S if for every set Y subset of E of size at most q, if there is a set X is an element of S disjoint from Y with X boolean OR Y is an element of I, then there is a set (X) over cap is an element of(S) over cap disjoint from Y with (X) over cap boolean OR Y is an element of I. By the classic result of Bollobas, in a uniform matroid, every family of sets of size p has a q-representative family with at most ((p+q) (p)) sets. In his famous "two families theorem" from 1977, Lovasz 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+q) (p)) in time bounded by a polynomial in ((p+q) (p)), t, and the time required for field operations. We demonstrate how the efficient construction of representative families can be a powerful tool for designing single-exponential parameterized and exact exponential time algorithms. The applications of our approach include the following: -In the LONG DIRECTED CYCLE problem, the input is a directed n-vertex graph G and the positive integer k. The task is to find a directed cycle of length at least k in G, if such a cycle exists. As a consequence of our 6.75(k+o(k))n(O(1)) time algorithm, we have that a directed cycle of length at least log n, if such a cycle exists, can be found in polynomial time. -In the MINIMUM EQUIVALENT GRAPH (MEG) problem, we are seeking a spanning subdigraph D' of a given n-vertex digraph D with as few arcs as possible in which the reachability relation is the same as in the original digraph D. -We provide an alternative proof of the recent results for algorithms on graphs of bounded treewidth showing that many "connectivity" problems such as HAMILTONIAN CYCLE or STEINER TREE can be solved in time 2(O(t)) n on n-vertex graphs of treewidth at most t. For the special case of uniform matroids on nelements, we give a faster algorithm to compute a representative family. We use this algorithm to provide the fastest known deterministic parameterized algorithms for kPATH, k-TREE, and, more generally, k-SUBGRAPH ISOMORPHISM, where the k-vertex pattern graph is of constant treewidth.