Exact Covers via Determinants

Andreas BjöRklund
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...