Counting Edge-injective Homomorphisms and Matchings on Restricted Graph Classes

Radu-Cristian Curticapean, Holger Dell, Marc Roth

Research output: Journal Article or Conference Article in JournalJournal articleResearchpeer-review


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 viewed as edge-injective homomorphisms from the disjoint union of k length-2 paths into (arbitrary) host graphs. Here, a homomorphism from H to G is edge-injective if it maps any two distinct edges of H to distinct edges in G. We show that edge-injective homomorphisms from a pattern graph H can be counted in polynomial time if H has bounded vertex-cover number after removing isolated edges. For hereditary classes H of pattern graphs, we complement this result: If the graphs in H have unbounded vertex-cover number even after deleting isolated edges, then counting edge-injective homomorphisms with patterns from H is #W[1]-hard. Our proofs rely on an edge-colored variant of Holant problems and a delicate interpolation argument; both may be of independent interest.
Original languageEnglish
JournalTheory of Computing Systems
Pages (from-to)1-40
Number of pages40
Publication statusPublished - 31 Oct 2018
Externally publishedYes


  • Parameterized complexity
  • Counting complexity
  • Line graphs
  • Homomorphisms
  • Matchings


Dive into the research topics of 'Counting Edge-injective Homomorphisms and Matchings on Restricted Graph Classes'. Together they form a unique fingerprint.

Cite this