Approximately Counting H-Colourings is $$\#\mathrm {BIS}$$-Hard

DOI10.1007/978-3-662-47672-7_43zbMath1342.68146arXiv1502.01335OpenAlexW2226816827MaRDI QIDQ3448813

Leslie Ann Goldberg, Andreas Galanis, Mark R. Jerrum

Publication date: 27 October 2015

Published in: Automata, Languages, and Programming (Search for Journal in Brave)

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

Mathematics Subject Classification ID

Enumeration in graph theory (05C30) Coloring of graphs and hypergraphs (05C15) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Approximation algorithms (68W25) Randomized algorithms (68W20)

Cites Work

• A counterexample to rapid mixing of the Ge-Stefankovic process
• On the hardness of sampling independent sets beyond the tree threshold
• Random generation of combinatorial structures from a uniform distribution
• On the complexity of H-coloring
• The relative complexity of approximate counting problems
• Counting and sampling \(H\)-colourings
• The Complexity of Choosing an H-Coloring (Nearly) Uniformly at Random
• Operations with structures
• Unnamed Item
• Unnamed Item