The complexity of counting surjective homomorphisms and compactions

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

Leslie Ann Goldberg, S. Zivny, Jacob Focke

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?)
• Counting graph homomorphisms
• Title not available (Why is that?)
• Title not available (Why is that?)
• On the complexity of H-coloring
• The relative complexity of approximate counting problems
• The complexity of surjective homomorphism problems-a survey
• Graph homomorphisms and phase transitions
• Title not available (Why is that?)
• Title not available (Why is that?)
• Left and right convergence of graphs with bounded degree
• List homomorphisms and circular arc graphs
• List homomorphisms to reflexive graphs
• 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
• Compaction, Retraction, and Constraint Satisfaction
• Computational Complexity of Compaction to Reflexive Cycles
• Computational complexity of compaction to irreflexive cycles
• Retractions to Pseudoforests
• Computing vertex-surjective homomorphisms to partially reflexive trees
• Title not available (Why is that?)
• Operations with structures
• The computational complexity of disconnected cut and \(2 K_2\)-partition
• Finding vertex-surjective graph homomorphisms
• Homomorphisms of graphs and of their orientations
• Homomorphisms are a good basis for counting small subgraphs
• Title not available (Why is that?)
• Surjective H-colouring: New hardness results
• Probability and computing. Randomization and probabilistic techniques in algorithms and data analysis
• Approximately counting \(H\)-colorings is \(\#\)BIS-hard
• Counting Homomorphisms to Square-Free Graphs, Modulo 2

Cited In (3)

• The complexity of locally injective homomorphisms
• Algebraic global gadgetry for surjective constraint satisfaction
• Title not available (Why is that?)

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)