<p>Our recent paper shows that counting k-matchings is #W[1]-hard even in bipartite graphs. This answers your question.</p>

<p><a href="http://arxiv.org/abs/1407.2929">Radu Curticapean, Dániel Marx: Complexity of counting subgraphs: only the boundedness of the vertex-cover number counts. CoRR abs/1407.2929 (2014)</a></p>

CC BY-SA 3.0
2014-08-28T11:26:17.180Z
2014-08-28T11:26:17.180Z
Daniel Marx
<p>Radu Curticapean showed that counting matchings of size k is #W[1]-Hard. See <a href="http://link.springer.com/chapter/10.1007/978-3-642-39206-1_30" rel="nofollow">http://link.springer.com/chapter/10.1007/978-3-642-39206-1_30</a></p>

CC BY-SA 3.0
2014-08-12T16:27:29.953Z
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
CC BY-SA 3.0
2014-08-12T17:37:23.673Z
You are right. Sorry I missed the "bipartite" constraint...
Heng Guo
CC BY-SA 3.0
2014-08-12T16:21:18.070Z
2014-08-12T16:21:18.070Z
Heng Guo
<p>The $q$-Dimensional $p$-Matching is defined as follows:</p>

<p>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$. </p>

<p>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}$.</p>

<p>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$.</p>

<hr>

<p>In their <a href="http://web.stanford.edu/~rrwill/presentations/counting-k-paths.pdf" rel="nofollow">famous paper</a> from 2004, Flum and Grohe have developed the $\#W$ hierarchy, the counting equivalent of the $W$ hierarchy for parameterized problem.</p>

<p>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.</p>

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

<blockquote>
  <p>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$?</p>
</blockquote>

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

<hr>

<p>Related result: </p>

<p><a href="http://link.springer.com/chapter/10.1007%2F978-3-642-33293-7_17" rel="nofollow">Recent result</a> by Bläser and Curticapean shows that <em>weighted</em> counting of $k$-matching in bipartite graphs is $\#W[1]$-complete.</p>

<counting-complexity><parameterized-complexity><matching><fixed-parameter-tractable>
Is it known whether counting $q$-dimensional $p$-matching is $\#W[1]$-Hard?
R B
# Is it known whether counting $q$-dimensional $p$-matching is $\#W[1]$-Hard?

(Asked by: username_0 on 2014-08-12)

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](http://web.stanford.edu/~rrwill/presentations/counting-k-paths.pdf) 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](http://link.springer.com/chapter/10.1007%2F978-3-642-33293-7_17) by Bläser and Curticapean shows that *weighted* counting of $k$-matching in bipartite graphs is $\#W[1]$-complete.

**Tags:** counting-complexity, parameterized-complexity, matching, fixed-parameter-tractable


---

## 2 answers

### Answer by username_1 on 2014-08-28. Score: 8 | Accepted answer

Our recent paper shows that counting k-matchings is #W[1]-hard even in bipartite graphs. This answers your question.

[Radu Curticapean, Dániel Marx: Complexity of counting subgraphs: only the boundedness of the vertex-cover number counts. CoRR abs/1407.2929 (2014)](http://arxiv.org/abs/1407.2929)


---

### Answer by username_2 on 2014-08-12. Score: 0

Radu Curticapean showed that counting matchings of size k is #W[1]-Hard. See <http://link.springer.com/chapter/10.1007/978-3-642-39206-1_30>

> **Comments:**
> **username_0**: 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).  
> **username_2**: You are right. Sorry I missed the "bipartite" constraint...  

---

