Is it known whether counting $q$-dimensional $p$-matching is $\#W[1]$-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[1]$-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[1]$-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 Blser and Curticapean shows that weighted counting of $k$-matching in bipartite graphs is $\#W[1]$-complete.

Asked by user21001 (9,378 )
Aug 12, 2014 at 15:28