Exact Covers via Determinants

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.