The complexity of counting surjective homomorphisms and compactions

DOI10.1137/17M1153182zbMATH Open1429.05143WikidataQ127624736 ScholiaQ127624736MaRDI QIDQ5232140FDOQ5232140

Authors: Jacob Focke, Leslie Ann Goldberg, S. Zivny 

Publication date: 29 August 2019

Published in: SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

Recommendations

• The complexity of counting surjective homomorphisms and compactions
• The complexity of surjective homomorphism problems-a survey
• Surjective \(H\)-colouring: new hardness results
• scientific article; zbMATH DE number 1545676
• scientific article; zbMATH DE number 2151253

zbMATH Keywords

graph homomorphismscounting complexitysurjective homomorphismsgraph compactions

Mathematics Subject Classification ID

Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60) Enumeration in graph theory (05C30)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• A complete and equal computational complexity classification of compaction and retraction to all graphs with at most four vertices and some general results
• Algorithms for partition of some class of graphs under compaction and vertex-compaction
• Approximately counting \(H\)-colorings is \(\#\)BIS-hard
• Compaction, Retraction, and Constraint Satisfaction
• Computational Complexity of Compaction to Reflexive Cycles
• Computational complexity of compaction to irreflexive cycles
• Computing vertex-surjective homomorphisms to partially reflexive trees
• Counting graph homomorphisms
• Finding vertex-surjective graph homomorphisms
• Graph homomorphisms and phase transitions
• Homomorphisms are a good basis for counting small subgraphs
• Homomorphisms of graphs and of their orientations
• Large networks and graph limits
• Left and right convergence of graphs with bounded degree
• List homomorphisms and circular arc graphs
• List homomorphisms to reflexive graphs
• On the complexity of H-coloring
• Operations with structures
• Probability and computing. Randomization and probabilistic techniques in algorithms and data analysis
• Retractions to Pseudoforests
• Surjective \(H\)-colouring: new hardness results
• The complexity of surjective homomorphism problems-a survey
• The computational complexity of disconnected cut and \(2 K_2\)-partition
• The relative complexity of approximate counting problems

Cited In (5)

• The complexity of surjective homomorphism problems-a survey
• The complexity of locally injective homomorphisms
• Algebraic global gadgetry for surjective constraint satisfaction
• Title not available (Why is that?)
• The complexity of counting surjective homomorphisms and compactions

This page was built for publication: The complexity of counting surjective homomorphisms and compactions

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5232140)