Given a $k$-uniform hypergraph $G$ (i.e., each edge of $G$ contains precisely $k$ vertices) on $n$ vertices, the $k$-Exact Cover problem is the task of deciding if there exists $n/k$ edges in $G$ which together cover all the vertices of $G$. The counting version of this problem asks us to count the number of sets of $n/k$ edges in $G$ with this property.

If $G$ has the further property that it is $k$-partite, then this problem is referred to as $k$-Dimensional Matching.

Question 1: For $k\ge 3$, what are the fastest known algorithms for solving the decision and counting version of $k$-Exact Cover and $k$-dimensional Matching for each $k$?

When $k = 2$, these problems correspond to detecting and counting perfect matchings in general graphs and bipartite graphs. The detection problem is known to be in polynomial time, and the counting problem can be solved in both cases in $2^{n/2}\text{poly}(n)$ time (doing much better would correspond to getting better algorithms for computing matrix permanent, which seems to be a difficult problem).

This work of Andreas Björklund implies that the detection problem for $k$-Dimensional Matching can be solved in $2^{(1 - 2/k)n}$, and seems to reference that counting solutions can be done in $2^{(1-1/k)n}$ time. Is anything better known?

Question 2: For $k\ge 3$, are there any interesting (conditional) lower bounds on the parameterized complexity of solving $k$-Exact Cover or $k$-Dimensional Matching?

For example, are there any popular conjectures ruling out $2^{n - n/\omega(k)}$ time algorithms for these problems?


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.