Approximately counting H-colorings is \#BIS-hard

DOI10.1137/15M1020551zbMATH Open1342.68147MaRDI QIDQ2810271FDOQ2810271

Authors: Andreas Galanis, Leslie Ann Goldberg, Mark Jerrum 

Publication date: 1 June 2016

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

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

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)

Cites Work

• Title not available (Why is that?)
• 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
• A graph polynomial for independent sets of bipartite graphs
• The Complexity of Ferromagnetic Ising with Local Fields
• A counterexample to rapid mixing of the Ge-Stefankovic process
• Diophantine approximations and diophantine equations
• Title not available (Why is that?)
• Operations with structures
• Counting and sampling \(H\)-colourings
• The Complexity of Choosing an H-Coloring (Nearly) Uniformly at Random

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
• Title not available (Why is that?)
• Approximately counting locally-optimal structures
• Completeness results for counting problems with easy decision
• Title not available (Why is that?)
• 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
• Title not available (Why is that?)
• Approximately counting \(H\)-colourings is \(\#\mathrm{BIS}\)-hard
• Title not available (Why is that?)
• The Complexity of Choosing an H-Coloring (Nearly) Uniformly at Random

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)