6
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ If I were you, I would rather ask this on cstheory.stackexchange.com. You should also emphasize what kind of solution you're looking for (tractable in $k$?) and especially what the role of weights is in question 3. $\endgroup$
    – domotorp
    Jan 19, 2018 at 10:13
  • $\begingroup$ Would randomization, do better, for $k$ - regular, hyper graphs? Instead of straight forward set packing, mentioned in answer would triangle packings do better with a randomized algorithm? If, Markov Chains would be a help in calculating the matchcings.. $\endgroup$ Jan 22, 2018 at 22:53

1 Answer 1

4
+50
$\begingroup$

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.

$\endgroup$
3
  • $\begingroup$ is that k-uniform or k-regular, same? $\endgroup$ Jan 22, 2018 at 8:33
  • $\begingroup$ Yes, sorry. By $k$-uniform I mean each edge has vertices. Uniform is the term I as used to seeing used for this. $\endgroup$ Jan 22, 2018 at 13:56
  • $\begingroup$ *(correction to above comment) "... each edge has $k$ vertices..." $\endgroup$ Jan 22, 2018 at 16:55

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.