The complexity of counting colourings and independent sets in sparse graphs and hypergraphs
From MaRDI portal
Publication:1590082
DOI10.1007/PL00001601zbMath0963.68082OpenAlexW2094731577MaRDI QIDQ1590082
Publication date: 19 December 2000
Published in: Computational Complexity (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/pl00001601
Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Coloring of graphs and hypergraphs (05C15)
Related Items (23)
Approximately Counting Independent Sets of a Given Size in Bounded-Degree Graphs ⋮ Counting Maximal Independent Sets in Subcubic Graphs ⋮ The complexity of weighted Boolean \#CSP with mixed signs ⋮ A Method for Computing the Merrifield–Simmons Index on Benzenoid Systems ⋮ Computational complexity of counting problems on 3-regular planar graphs ⋮ Algorithms for four variants of the exact satisfiability problem ⋮ Towards a dichotomy theorem for the counting constraint satisfaction problem ⋮ Holographic reduction, interpolation and hardness ⋮ On vertex independence number of uniform hypergraphs ⋮ Zeros, chaotic ratios and the computational complexity of approximating the independence polynomial ⋮ Inapproximability of the Partition Function for the Antiferromagnetic Ising and Hard-Core Models ⋮ Factor models on locally tree-like graphs ⋮ Improved mixing condition on the grid for counting and sampling independent sets ⋮ Convergence of MCMC and Loopy BP in the Tree Uniqueness Region for the Hard-Core Model ⋮ Organization mechanism and counting algorithm on vertex-cover solutions ⋮ On the complexity of finding and counting solution-free sets of integers ⋮ Counting independent sets in graphs with bounded bipartite pathwidth ⋮ Counting houses of Pareto optimal matchings in the house allocation problem ⋮ Faster graph coloring in polynomial space ⋮ Ferromagnetic Potts Model: Refined #BIS-hardness and Related Results ⋮ Spectral Independence in High-Dimensional Expanders and Applications to the Hardcore Model ⋮ Unnamed Item ⋮ Improved inapproximability results for counting independent sets in the hard-core model
This page was built for publication: The complexity of counting colourings and independent sets in sparse graphs and hypergraphs
