The complexity of counting surjective homomorphisms and compactions

DOI10.1137/17M1153182MaRDI QIDQ5232140zbMATH OpenWikidataFDO

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)

Full work available at URL https://doi.org/10.1137/17M1153182

zbMATH Keywords

counting complexitygraph compactionsgraph homomorphismssurjective homomorphisms

Mathematics Subject Classification ID

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

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

Cites work

• 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 irreflexive cycles
• Computational Complexity of Compaction to Reflexive 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
• scientific article; zbMATH DE number 3758365 (Why is no real title available?)
• scientific article; zbMATH DE number 610968 (Why is no real title available?)
• scientific article; zbMATH DE number 1545676 (Why is no real title available?)
• scientific article; zbMATH DE number 2151250 (Why is no real title available?)
• scientific article; zbMATH DE number 2151253 (Why is no real title available?)
• scientific article; zbMATH DE number 2117181 (Why is no real title available?)
• 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

(6)

• The complexity of surjective homomorphism problems-a survey
• The complexity of counting surjective homomorphisms and compactions
• scientific article; zbMATH DE number 769607 (Why is no real title available?)
• Algebraic global gadgetry for surjective constraint satisfaction
• The complexity of locally injective homomorphisms
• On counting (quantum-)graph homomorphisms in finite fields of prime order

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)