# Is it known whether counting $q$-dimensional $p$-matching is $\#W$-Hard?

The $q$-Dimensional $p$-Matching is defined as follows:

Given disjoint universes $U_1,\ldots,U_q$, think of an element in $U_1\times\ldots\times U_q$ as a set that contains exactly one element from each universe $U_i$.

Now, given a family ${\cal S}\subseteq U_1\times \ldots\times U_q$ and a parameter $k\in\mathbb{N}$, determine if there exists a subfamily of $k$ pairwise-disjoint sets in ${\cal S}$.

We abbreviate by $\#q$-Dimensional $p$-Matching (or $\#(q,p)$-matching in short) the counting version of the problem, asking how many matchings exist in $\cal S$.

In their famous paper from 2004, Flum and Grohe have developed the $\#W$ hierarchy, the counting equivalent of the $W$ hierarchy for parameterized problem.

Among their results in the paper, they have shown that counting the number of $k$-paths is $\#W$-complete, and conjectured that counting the number of matchings of size $k$ in a bipartite graph is hard as well.

I'm unaware of any results addressing this conjecture, but was wondering about even a weaker result:

Is #$q$-Dimensional $p$-Matching (counting the number of instances in a $(q,p)$-matching instace) $\#W$-complete, where the parameter is $p+q$?

Such result would be weaker than the FG's conjuncture, as counting bipartite matchings is the same as $\#(2,p)$-matching.

Related result:

Recent result by Bläser and Curticapean shows that weighted counting of $k$-matching in bipartite graphs is $\#W$-complete.

• True, but this doesn't answer the question.. This result is for general graphs and it's not translatable to #$q$-dimensional $p$-matching, but rather to #$(2,p)$-Set Packing (the problem is that the sets (edges by the graph formulation) may be arbitrary and not two items from two disjoint universes). – R B Aug 12 '14 at 16:27