Counting edge-injective homomorphisms and matchings on restricted graph classes

We consider the #W[1]-hard problem of counting all matchings with exactly k edges in a given input graph G; we prove that it remains #W[1]-hard on graphs G that are line graphs or bipartite graphs with degree 2 on one side. In our proofs, we use that k-matchings in line graphs can be equivalently vi...

תיאור מלא

מידע ביבליוגרפי
Main Authors: Curticapean, R, Dell, H, Roth, M
פורמט: Journal article
שפה:English
יצא לאור: Springer Nature 2018