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

DOI10.1137/15M1020551zbMath1342.68147MaRDI QIDQ2810271

Andreas Galanis, Leslie Ann Goldberg, Mark R. Jerrum

Publication date: 1 June 2016

Published in: SIAM Journal on Computing (Search for Journal in Brave)

zbMATH Keywords

graph homomorphismsapproximate counting\(H\)-coloringscounting independent sets in bipartite graphs

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)

Related Items

Completeness Results for Counting Problems with Easy Decision, Lower bounds for testing graphical models: colorings and antiferromagnetic Ising models, Counting Constraint Satisfaction Problems., Faster exponential-time algorithms for approximately counting independent sets, Unnamed Item, Unnamed Item, Unnamed Item, The Complexity of Counting Surjective Homomorphisms and Compactions, Unnamed Item, Counting Homomorphisms to $K_4$-Minor-Free Graphs, Modulo 2

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• 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
• Diophantine approximations and diophantine equations
• The relative complexity of approximate counting problems
• Counting and sampling \(H\)-colourings
• The Complexity of Ferromagnetic Ising with Local Fields
• The Complexity of Choosing an H-Coloring (Nearly) Uniformly at Random
• Operations with structures