Holographic Algorithms with Matchgates Capture Precisely Tractable Planar #CSP

DOI10.1137/16M1073984zbMath1370.68117arXiv1008.0683MaRDI QIDQ5737812

Pinyan Lu, Mingji Xia, Jin-Yi Cai

Publication date: 30 May 2017

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

Full work available at URL: https://arxiv.org/abs/1008.0683

zbMATH Keywords

\#Pcounting problemsdichotomy theoremsholographic algorithms

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

On Planar Boolean CSP ⋮ On blockwise symmetric matchgate signatures and higher domain \#CSP ⋮ The complexity of counting edge colorings and a dichotomy for some higher domain Holant problems ⋮ Nonnegative Weighted #CSP: An Effective Complexity Dichotomy ⋮ Counting Small Induced Subgraphs Satisfying Monotone Properties ⋮ Holographic Algorithm with Matchgates Is Universal for Planar \#CSP over Boolean Domain ⋮ Tensors masquerading as matchgates: relaxing planarity restrictions on Pfaffian circuits ⋮ Holographic algorithms by Fibonacci gates ⋮ Holographic algorithms on domains of general size ⋮ Holographic reduction for some counting problems ⋮ On the construction of graphs with a planar bipartite double cover from Boolean formulas and its application to counting satisfying solutions ⋮ Holographic algorithms beyond matchgates ⋮ A collapse theorem for holographic algorithms with matchgates on domain size at most 4 ⋮ Progress in Complexity of Counting Problems ⋮ Holographic algorithms on bases of rank 2 ⋮ The complexity of planar Boolean \#CSP with complex weights ⋮ Parameterized counting of partially injective homomorphisms ⋮ The Complexity of Symmetric Boolean Parity Holant Problems ⋮ Bipartite 3-regular counting problems with mixed signs ⋮ Bipartite 3-regular counting problems with mixed signs ⋮ A Complete Dichotomy Rises from the Capture of Vanishing Signatures ⋮ Counting edge-injective homomorphisms and matchings on restricted graph classes ⋮ FKT is not universal -- a planar holant dichotomy for symmetric constraints ⋮ A dichotomy for real weighted Holant problems

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• The complexity of computing the permanent
• Towards a dichotomy theorem for the counting constraint satisfaction problem
• Basis collapse in holographic algorithms
• On symmetric signatures in holographic algorithms
• Expressiveness of matchgates.
• From Holant to \#CSP and back: dichotomy for Holant\(^{c}\) problems
• Valiant's holant theorem and matchgate tensors
• Computational complexity of counting problems on 3-regular planar graphs
• The complexity of partition functions
• The Complexity of Counting in Sparse, Regular, and Planar Graphs
• The statistics of dimers on a lattice
• Holant Problems for Regular Graphs with Complex Edge Functions
• Quantum Circuits That Can Be Simulated Classically in Polynomial Time
• Statistical mechanics, three-dimensionality and NP-completeness
• Reflection positivity, rank connectivity, and homomorphism of graphs
• The Complexity of the Counting Constraint Satisfaction Problem
• Holographic Algorithms
• On counting homomorphisms to directed acyclic graphs
• Some Results on Matchgates and Holographic Algorithms
• A Computational Proof of Complexity of Some Restricted Counting Problems
• The Complexity of Enumeration and Reliability Problems
• Tensor Geometry
• Beitrag zur Theorie des Ferromagnetismus
• Holant problems and counting CSP
• Classification of a Class of Counting Problems Using Holographic Reductions
• Dimer problem in statistical mechanics-an exact result
• Automata, Languages and Programming
• A complete dichotomy rises from the capture of vanishing signatures
• The Spontaneous Magnetization of a Two-Dimensional Ising Model
• Statistical Theory of Equations of State and Phase Transitions. I. Theory of Condensation
• Statistical Theory of Equations of State and Phase Transitions. II. Lattice Gas and Ising Model
• Crystal Statistics. I. A Two-Dimensional Model with an Order-Disorder Transition
• The Complexity of Symmetric Boolean Parity Holant Problems
• Graph Homomorphisms with Complex Values: A Dichotomy Theorem