A complexity dichotomy for hypergraph partition functions

DOI10.1007/s00037-010-0300-6zbMath1217.68105arXiv0811.0037WikidataQ56323827 ScholiaQ56323827MaRDI QIDQ626694

Leslie Ann Goldberg, Martin Dyer, Mark R. Jerrum

Publication date: 18 February 2011

Published in: Computational Complexity (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/0811.0037

zbMATH Keywords

dichotomy theorem; complexity of counting homomorphisms

Mathematics Subject Classification ID

68Q25: Analysis of algorithms and problem complexity

68R05: Combinatorics in computer science

68R10: Graph theory (including graph drawing) in computer science

08A70: Applications of universal algebra in computer science

68Q17: Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)

Related Items

The complexity of weighted and unweighted \(\#\)CSP