Counting edge-injective homomorphisms and matchings on restricted graph classes

This is the authors' abstract. We don't add key points for this paper.

We consider the #[1]-hard problem of counting all matchings with k edges in a given input graph G; we prove that it remains#[1]-hard on graphs G that are line graphs or bipartite graphs degree $2$ on one side. In our proofs, we use that k-matchings in line can be equivalently viewed as edge-injective homomorphisms from the union of k length-$2$ paths into (arbitrary) host graphs. Here, a from H to G is edge-injective if it maps any two distinct of H to distinct edges in G. We show that edge-injective from a pattern graph H can be counted in polynomial time if H bounded vertex-cover number after removing isolated edges. For hereditary of pattern graphs, we complement this result: If the in have unbounded vertex-cover number even after deleting edges, then counting edge-injective homomorphisms with patterns from is #[1]-hard. Our proofs rely on an edge-colored of Holant problems and a delicate interpolation argument; both may be independent interest.