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://drops.dagstuhl.de/opus/volltexte/2010/2447/
 Go to the corresponding LIPIcs Volume Portal

### Exact Covers via Determinants

 pdf-format:

### 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},
annote =	{Keywords: Moderately Exponential Time Algorithms, Exact Set Cover, $k$-Dimensional Matching}

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