Anzeige
Erschienen in:
2012 | OriginalPaper | Buchkapitel
Weighted Counting of k-Matchings Is #W[1]-Hard
verfasst von : Markus Bläser, Radu Curticapean
Erschienen in: Parameterized and Exact Computation
Verlag: Springer Berlin Heidelberg
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
In the seminal paper for parameterized counting complexity [1], the following problem is conjectured to be #W[1]-hard: Given a bipartite graph
G
and a number
k
∈ ℕ, which is considered as a parameter, count the number of matchings of size
k
in
G
.
We prove hardness for a natural weighted generalization of this problem: Let
G
= (
V
,
E
,
w
) be an edge-weighted graph and define the weight of a matching as the product of weights of all edges in the matching. We show that exact evaluation of the sum over all such weighted matchings of size
k
is #W[1]-hard for bipartite graphs
G
.
As an intermediate step in our reduction, we also prove #W[1]- hardness of the problem of counting
k
-partial cycle covers, which are vertex-disjoint unions of cycles including
k
edges in total. This hardness result even holds for unweighted graphs.