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](https://en.wikipedia.org/wiki/Hafnian) of the corresponding $n \times n$ [adjacency matrix](https://en.wikipedia.org/wiki/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](https://en.wikipedia.org/wiki/Computing_the_permanent). $perm(A)$ can be evaluated in $O(2^{n-1}n^2)$ steps.


For $k>2$, the hypergraphs can be written as [incidence matrix](https://en.wikipedia.org/wiki/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.



Complexity for calculating number of Perfect Matchings in k-regular hypergraph
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.


