License: Creative Commons Attribution-NoDerivs 3.0 Unported license (CC BY-ND 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.STACS.2010.2447
URN: urn:nbn:de:0030-drops-24474
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2010/2447/
Go to the corresponding LIPIcs Volume Portal

Björklund, Andreas

Exact Covers via Determinants

pdf-format:
1001.BjoerklundAndreas.pdf (0.3 MB)

Abstract

Given a $k$-uniform hypergraph on $n$ vertices, partitioned in $k$ equal parts such that every hyperedge includes one vertex from each part, the $k$-Dimensional Matching problem asks whether there is a disjoint collection of the hyperedges which covers all vertices.
We show it can be solved by a randomized polynomial space algorithm in $O^*(2^{n(k-2)/k})$ time. The $O^*()$ notation hides factors
polynomial in $n$ and $k$.

The general Exact Cover by $k$-Sets problem asks the same when the partition constraint is dropped and arbitrary hyperedges of cardinality $k$ are permitted. We show it can be solved by a randomized polynomial space algorithm in $O^*(c_k^n)$ time, where $c_3=1.496, c_4=1.642, c_5=1.721$, and provide a general bound for larger $k$.

Both results substantially improve on the previous best algorithms for these problems, especially for small $k$. They follow from the new observation that Lov\'asz' perfect matching detection via determinants (Lov\'asz, 1979) admits an embedding in the recently proposed inclusion--exclusion counting scheme for set covers, \emph{despite} its inability to count the perfect matchings.

BibTeX - Entry

@InProceedings{bjrklund:LIPIcs:2010:2447,
  author =	{Andreas Bj{\"o}rklund},
  title =	{{Exact Covers via Determinants}},
  booktitle =	{27th International Symposium on Theoretical Aspects of Computer Science},
  pages =	{95--106},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-16-3},
  ISSN =	{1868-8969},
  year =	{2010},
  volume =	{5},
  editor =	{Jean-Yves Marion and Thomas Schwentick},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2010/2447},
  URN =		{urn:nbn:de:0030-drops-24474},
  doi =		{10.4230/LIPIcs.STACS.2010.2447},
  annote =	{Keywords: Moderately Exponential Time Algorithms, Exact Set Cover, $k$-Dimensional Matching}
}

Keywords: Moderately Exponential Time Algorithms, Exact Set Cover, $k$-Dimensional Matching
Collection: 27th International Symposium on Theoretical Aspects of Computer Science
Issue Date: 2010
Date of publication: 09.03.2010

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI