Computational complexity of counting problems on 3-regular planar graphs

DOI10.1016/j.tcs.2007.05.023zbMath1124.68083OpenAlexW2056017121MaRDI QIDQ2382289

Mingji Xia, Peng Zhang, Wen-Bo Zhao

Publication date: 28 September 2007

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2007.05.023

zbMATH Keywords

matchingvertex coverholographic reduction{\#}P-completeness

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Related Items

Some observations on holographic algorithms ⋮ Counting Homomorphisms to Square-Free Graphs, Modulo 2 ⋮ Holant problems for 3-regular graphs with complex edge functions ⋮ A Graph Polynomial for Independent Sets of Bipartite Graphs ⋮ Complexity of Ising Polynomials ⋮ Holographic reduction, interpolation and hardness ⋮ Partition functions on \(k\)-regular graphs with \(\{0,1\}\)-vertex assignments and real edge functions ⋮ Tensor network contractions for \#SAT ⋮ Holographic algorithms by Fibonacci gates ⋮ From Holant to \#CSP and back: dichotomy for Holant\(^{c}\) problems ⋮ Holographic algorithms: from art to science ⋮ Holographic algorithms on domains of general size ⋮ The challenges of unbounded treewidth in parameterised subgraph counting problems ⋮ Unnamed Item ⋮ Counting polygon triangulations is hard ⋮ Faster exponential-time algorithms for approximately counting independent sets ⋮ Spin systems on \(k\)-regular graphs with complex edge functions ⋮ Holographic Algorithms with Matchgates Capture Precisely Tractable Planar #CSP ⋮ A fixed-parameter perspective on \#BIS ⋮ Unnamed Item ⋮ Parameterized counting of partially injective homomorphisms ⋮ Satisfaction and power in unanimous majority influence decision models ⋮ Unnamed Item ⋮ Counting edge-injective homomorphisms and matchings on restricted graph classes ⋮ Counting Restricted Homomorphisms via Möbius Inversion over Matroid Lattices

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• The complexity of counting self-avoiding walks in subgraphs of two-dimensional grids and hypercubes.
• The complexity of counting colourings and independent sets in sparse graphs and hypergraphs
• Complexity of generalized satisfiability counting problems
• The Complexity of Counting in Sparse, Regular, and Planar Graphs
• The statistics of dimers on a lattice
• Statistical Mechanics of Dimers on a Plane Lattice
• Some Results on Matchgates and Holographic Algorithms
• The Complexity of Enumeration and Reliability Problems
• The Complexity of Planar Counting Problems
• Dimer problem in statistical mechanics-an exact result
• Theory and Applications of Models of Computation
• Theory and Applications of Models of Computation