Computational complexity of counting problems on 3-regular planar graphs

DOI10.1016/J.TCS.2007.05.023MaRDI QIDQ2382289zbMATH OpenOpenAlexFDO

Authors 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)

Recommendations

• The complexity of counting in sparse, regular, and planar graphs
• Theory and Applications of Models of Computation
• A computational proof of complexity of some restricted counting problems
• Holant problems for 3-regular graphs with complex edge functions
• A Computational Proof of Complexity of Some Restricted Counting Problems

Cites work

• scientific article; zbMATH DE number 610968 (Why is no real title available?)
• scientific article; zbMATH DE number 6472599 (Why is no real title available?)
• scientific article; zbMATH DE number 3326387 (Why is no real title available?)
• Complexity of generalized satisfiability counting problems
• Dimer problem in statistical mechanics-an exact result
• Some Results on Matchgates and Holographic Algorithms
• Statistical Mechanics of Dimers on a Plane Lattice
• The Complexity of Enumeration and Reliability Problems
• The Complexity of Planar Counting Problems
• The complexity of counting colourings and independent sets in sparse graphs and hypergraphs
• The complexity of counting in sparse, regular, and planar graphs
• The complexity of counting self-avoiding walks in subgraphs of two-dimensional grids and hypercubes.
• The statistics of dimers on a lattice. I: The number of dimer arrangements on a quadratic lattice
• Theory and Applications of Models of Computation
• Theory and Applications of Models of Computation

Cited in

(29)

• Counting restricted homomorphisms via Möbius inversion over matroid lattices
• Counting edge-injective homomorphisms and matchings on restricted graph classes
• A graph polynomial for independent sets of bipartite graphs
• scientific article; zbMATH DE number 7559233 (Why is no real title available?)
• A computational proof of complexity of some restricted counting problems
• Satisfaction and power in unanimous majority influence decision models
• Faster exponential-time algorithms for approximately counting independent sets
• Counting problems in parameterized complexity
• A fixed-parameter perspective on \#BIS
• A fixed-parameter perspective on \#BIS
• Complexity of Ising polynomials
• Parameterized counting of partially injective homomorphisms
• Holographic algorithms by Fibonacci gates
• From Holant to \#CSP and back: dichotomy for Holant\(^{c}\) problems
• Holant problems for 3-regular graphs with complex edge functions
• Holographic algorithms with matchgates capture precisely tractable planar \#CSP
• Partition functions on \(k\)-regular graphs with \(\{0,1\}\)-vertex assignments and real edge functions
• Holographic algorithms on domains of general size
• Tensor network contractions for \#SAT
• Holographic algorithms: from art to science
• Spin systems on k-regular graphs with complex edge functions
• Some observations on holographic algorithms
• Counting polygon triangulations is hard
• A Computational Proof of Complexity of Some Restricted Counting Problems
• Theory and Applications of Models of Computation
• The challenges of unbounded treewidth in parameterised subgraph counting problems
• Holographic reduction, interpolation and hardness
• On the construction of graphs with a planar bipartite double cover from Boolean formulas and its application to counting satisfying solutions
• The complexity of counting in sparse, regular, and planar graphs

This page was built for publication: Computational complexity of counting problems on 3-regular planar graphs

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