Approximately counting H-colorings is \#BIS-hard

DOI10.1137/15M1020551MaRDI QIDQ2810271zbMATH OpenFDO

Authors Andreas Galanis, Leslie Ann Goldberg, Mark 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

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

Recommendations

• Approximately counting \(H\)-colourings is \(\#\mathrm{BIS}\)-hard
• A Complexity Trichotomy for Approximately Counting List H -Colorings
• A complexity trichotomy for approximately counting list \(H\)-colourings
• The Complexity of Choosing an H-Coloring (Nearly) Uniformly at Random
• Counting and sampling \(H\)-colourings

Cites work

• scientific article; zbMATH DE number 1545676 (Why is no real title available?)
• scientific article; zbMATH DE number 2117181 (Why is no real title available?)
• A counterexample to rapid mixing of the Ge-Stefankovic process
• A graph polynomial for independent sets of bipartite graphs
• Counting and sampling \(H\)-colourings
• Diophantine approximations and diophantine equations
• On the complexity of H-coloring
• On the hardness of sampling independent sets beyond the tree threshold
• Operations with structures
• Random generation of combinatorial structures from a uniform distribution
• The Complexity of Choosing an H-Coloring (Nearly) Uniformly at Random
• The Complexity of Ferromagnetic Ising with Local Fields
• The relative complexity of approximate counting problems

Cited in

(19)

• Lower bounds for testing graphical models: colorings and antiferromagnetic Ising models
• Faster exponential-time algorithms for approximately counting independent sets
• scientific article; zbMATH DE number 2019624 (Why is no real title available?)
• Counting Homomorphisms to $K_4$-Minor-Free Graphs, Modulo 2
• Hardness of identity testing for restricted Boltzmann machines and Potts models
• Counting homomorphisms modulo a prime number
• Counting constraint satisfaction problems
• The complexity of counting surjective homomorphisms and compactions
• Fast algorithms for general spin systems on bipartite expanders
• A fixed-parameter perspective on \#BIS
• A complexity trichotomy for approximately counting list \(H\)-colourings
• Approximately counting \(H\)-colourings is \(\#\mathrm{BIS}\)-hard
• scientific article; zbMATH DE number 7561704 (Why is no real title available?)
• Approximately counting locally-optimal structures
• On the approximation complexity hierarchy
• Counting and sampling \(H\)-colourings
• The Complexity of Choosing an H-Coloring (Nearly) Uniformly at Random
• Completeness results for counting problems with easy decision
• The complexity of counting colourings and independent sets in sparse graphs and hypergraphs

This page was built for publication: Approximately counting \(H\)-colorings is \(\#\)BIS-hard

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2810271)