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

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)