7
$\begingroup$

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 Bläser and Curticapean shows that weighted counting of $k$-matching in bipartite graphs is $\#W[1]$-complete.

$\endgroup$
8
$\begingroup$

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)

$\endgroup$
0
$\begingroup$

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

$\endgroup$
  • 1
    $\begingroup$ 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). $\endgroup$ – R B Aug 12 '14 at 16:27
  • 1
    $\begingroup$ You are right. Sorry I missed the "bipartite" constraint... $\endgroup$ – Heng Guo Aug 12 '14 at 17:37

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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