Abstract | ||
---|---|---|
Focke, Goldberg, and \v{Z}ivn\'y (arXiv 2017) prove a complexity dichotomy for the problem of counting surjective homomorphisms from a large input graph G without loops to a fixed graph H that may have loops. In this note, we give a short proof of a weaker result: Namely, we only prove the #P-hardness of the more general problem in which G may have loops. Our proof is an application of a powerful framework of Lov\'asz (2012), and it is analogous to proofs of Curticapean, Dell, and Marx (STOC 2017) who studied the "dual" problem in which the pattern graph G is small and the host graph H is the input. Independently, Chen (arXiv 2017) used Lov\'asz's framework to prove a complexity dichotomy for counting surjective homomorphisms to fixed finite structures. |
Year | Venue | DocType |
---|---|---|
2017 | CoRR | Journal |
Volume | Citations | PageRank |
abs/1710.01712 | 0 | 0.34 |
References | Authors | |
0 | 1 |
Name | Order | Citations | PageRank |
---|---|---|---|
Holger Dell | 1 | 220 | 16.74 |