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

Access Restriction
Subscribed

 Author Fomin, Fedor V. ♦ Lokshtanov, Daniel ♦ Panolan, Fahad ♦ Saurabh, Saket Source ACM Digital Library Content type Text Publisher Association for Computing Machinery (ACM) File Format PDF Copyright Year ©2016 Language English
 Subject Domain (in DDC) Computer science, information & general works ♦ Data processing & computer science Subject Keyword Matroids ♦ Hash functions ♦ Linear independence ♦ Parameterized algorithms ♦ Representative families Abstract Let $\textit{M}=(\textit{E},$ $\textit{I})$ be a matroid and let $S={S_{1},$ ċ , $S_{t}}$ be a family of subsets of $\textit{E}$ of size $\textit{p}.$ A subfamily $\textit{Ŝ}$ ⊆ $\textit{S}$ is $\textit{q}-\textit{representative}$ for $\textit{S}$ if for every set $\textit{Y}⊆\textit{E}$ of size at most $\textit{q},$ if there is a set $\textit{X}$ ∈ $\textit{S}$ disjoint from $\textit{Y}$ with $\textit{X}∪$ $\textit{Y}$ ∈ $\textit{I},$ then there is a set $\textit{&Xcirc;}$ ∈ $\textit{Ŝ}$ disjoint from $\textit{Y}$ with $\textit{&Xcirc;}$ ∪ $\textit{Y}$ ∈ $\textit{I}.$ By the classic result of Bollobás, in a uniform matroid, every family of sets of size $\textit{p}$ has a $\textit{q}-representative$ family with at most $(^{p+q}_{p})$ 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 $\textit{q}-representative$ family of size at most $(^{p+q}_{p})$ in time bounded by a polynomial in $(^{p+q}_{p}),$ $\textit{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 $\textit{n}-vertex$ graph $\textit{G}$ and the positive integer $\textit{k}.$ The task is to find a directed cycle of length at least $\textit{k}$ in $\textit{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 $\textit{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 $\textit{D}′$ of a given $\textit{n}-vertex$ digraph $\textit{D}$ with as few arcs as possible in which the reachability relation is the same as in the original digraph $\textit{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 $\textit{n}-vertex$ graphs of treewidth at most $\textit{t}.$ For the special case of uniform matroids on $\textit{n}$ elements, we give a faster algorithm to compute a representative family. We use this algorithm to provide the fastest known deterministic parameterized algorithms for $\textit{k}-Path,$ $\textit{k}-Tree,$ and, more generally, $\textit{k}-Subgraph$ Isomorphism, where the $\textit{k}-vertex$ pattern graph is of constant treewidth. Description Author Affiliation: University of Bergen, Bergen, Norway (Fomin, Fedor V.; Lokshtanov, Daniel); Institute of Mathematical Sciences, India, and University of Bergen, Bergen, Norway (Saurabh, Saket); Institute of Mathematical Sciences, Chennai, India (Panolan, Fahad) ISSN 00045411 Age Range 18 to 22 years ♦ above 22 year Educational Use Research Education Level UG and PG Learning Resource Type Article Publisher Date 2016-09-01 Publisher Place New York e-ISSN 1557735X Journal Journal of the ACM (JACM) Volume Number 63 Issue Number 4 Page Count 60 Starting Page 1 Ending Page 60

#### Open content in new tab

Source: ACM Digital Library