Access Restriction

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

   Open content in new tab
Source: ACM Digital Library