The Complexity of Counting Surjective Homomorphisms and Compactions
From MaRDI portal
Publication:5232140
DOI10.1137/17M1153182zbMath1429.05143WikidataQ127624736 ScholiaQ127624736MaRDI QIDQ5232140
Leslie Ann Goldberg, Stanislav Živný, Jacob Focke
Publication date: 29 August 2019
Published in: SIAM Journal on Discrete Mathematics (Search for Journal in Brave)
Enumeration in graph theory (05C30) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60)
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Algorithms for partition of some class of graphs under compaction and vertex-compaction
- The complexity of surjective homomorphism problems-a survey
- Computational complexity of compaction to irreflexive cycles
- Computing vertex-surjective homomorphisms to partially reflexive trees
- Finding vertex-surjective graph homomorphisms
- On the complexity of H-coloring
- List homomorphisms to reflexive graphs
- Homomorphisms of graphs and of their orientations
- Graph homomorphisms and phase transitions
- The relative complexity of approximate counting problems
- List homomorphisms and circular arc graphs
- The computational complexity of disconnected cut and \(2 K_2\)-partition
- A complete and equal computational complexity classification of compaction and retraction to all graphs with at most four vertices and some general results
- Approximately Counting $H$-Colorings is $\#\mathrm{BIS}$-Hard
- Retractions to Pseudoforests
- Counting Homomorphisms to Square-Free Graphs, Modulo 2
- Compaction, Retraction, and Constraint Satisfaction
- Computational Complexity of Compaction to Reflexive Cycles
- Left and right convergence of graphs with bounded degree
- Homomorphisms are a good basis for counting small subgraphs
- Surjective H-colouring: New hardness results
- Operations with structures
