Complexity for calculating number of Perfect Matchings in k-regular hypergraph

Question

Let $G(V,E)$ be a unweighted, k-regular hypergraph, with vertices $V=(v_1, ... v_n)$ and edges $E=(e_1, ... e_m)$. The k-regularity leads to $|e_i|=k$ (i.e. every edge contains exactly $k$ vertices). A perfect matching (PM) is a subset of $E$, such that every vertex $v_i$ is contained exactly one time.

A 2-regular hypergraph is a usual graph. To get the number of PMs, one calculates the Hafnian of the corresponding $n \times n$ adjacency matrix A. Calculating the Hafnian is in the complexity class $\#P$. For bipartite 2-regular graphs, one can calculate the permanent of the adjacency matrix via the Ryser formular. $perm(A)$ can be evaluated in $O(2^{n-1}n^2)$ steps.

For $k>2$, the hypergraphs can be written as incidence matrix or high-dimensional $n \times n \times ... \times n$ adjacency matrix A.

My three questions:

1. With which algorithm can the number of perfect matchings be calculated for unweighted k-regular graphs, and what is its runtime?

2. With which algorithm can the number of perfect matchings be calculated for a unweighted hypergraph with $|e_i|\leq k$, and what is its runtime?

3. With which algorithm can the number of perfect matchings be calculated for k-regular graphs with complex weights, and what is its runtime?

Any answer or link to literature would be highly appreciated.

Answer 1

In the literature this problem also goes by "set packing" which can help find references. The set-up in this language is given a universe $V$ of $n$ elements and family of subsets $E$ a packing is a collection of mutually disjoint sets from $E$ (i.e. a matching). A $t$-packing is a packing consisting of $t$ sets.

The problem of counting $t$-packings in the $k$-uniform case where each element of $E$ contains exactly $k$ elements is considered in

 Björklund, Andreas; Husfeldt, Thore; Kaski, Petteri; Koivisto, Mikko.
 Counting paths and packings in halves. Algorithms—ESA 2009, 578--586,
 Lecture Notes in Comput. Sci., 5757, Springer, Berlin, 2009. MR2557785

where it is shown that such $t$-packings can be counted in $O^*(\binom{n}{tk/2})$ time. Here $O^*$ suppresses a factor polynomial is the mentioned parameters. For perfect matching we need $tk = n$ so we end up with $O^*(\binom{n}{n/2})$. Methods in this approach use a disjoint sum problem, inclusion-exclusion, and dynamic programming. So, this provides some answer to question 1. It was the fastest algorithm I found, but I did not attempt to perform an exhaustive search of the literature. Perhaps this article, references within, and the term "set packing" can help to up further relevant information.

Also, again in the $k$-uniform case, parameterized by $t$ the problem of counting $t$-packing is shown to by $W[1]\#$-hard in

Liu, Yunlong; Wang, Jianxin. On counting parameterized matching and
packing. Frontiers in algorithmics, 125--134, Lecture Notes in Comput. 
Sci., 9711, Springer, [Cham], 2016. MR3571845

since there is a reduction with parameterized matching counting in graphs.