Name
Abstract | ||
|---|---|---|
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 \(\mathcal {H}\) of pattern graphs, we complement this result: If the graphs in \(\mathcal {H}\) have unbounded vertex-cover number even after deleting isolated edges, then counting edge-injective homomorphisms with patterns from \(\mathcal {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. |
Year | DOI | Venue |
|---|---|---|
2017 | 10.4230/LIPIcs.STACS.2017.25 | symposium on theoretical aspects of computer science |
Keywords | DocType | Volume |
Matchings, Homomorphisms, Line graphs, Counting complexity, Parameterized complexity | Conference | abs/1702.05447 |
ISSN | Citations | PageRank |
1868-8969 | 0 | 0.34 |
References | Authors | |
21 | 3 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Radu Curticapean | 1 | 70 | 8.75 |
| Holger Dell | 2 | 220 | 16.74 |
| Marc Roth | 3 | 1 | 2.05 |