The complexity of counting edge colorings and a dichotomy for some higher domain Holant problems
From MaRDI portal
Publication:313398
DOI10.1186/s40687-016-0067-8zbMath1344.05060arXiv1404.4020OpenAlexW2412274288WikidataQ59474470 ScholiaQ59474470MaRDI QIDQ313398
Heng Guo, Tyson Williams, Jin-Yi Cai
Publication date: 9 September 2016
Published in: Research in the Mathematical Sciences (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1404.4020
Graph polynomials (05C31) Separable extensions, Galois theory (12F10) Planar graphs; geometric and topological aspects of graph theory (05C10) Coloring of graphs and hypergraphs (05C15)
Related Items
Holographic Algorithm with Matchgates Is Universal for Planar \#CSP over Boolean Domain, Zeros and approximations of holant polynomials on the complex plane, A Markov chain on the solution space of edge colorings of bipartite graphs, The complexity of counting edge colorings for simple graphs, On the complexity of generalized chromatic polynomials
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- The complexity of complex weighted Boolean \#CSP
- Spin systems on \(k\)-regular graphs with complex edge functions
- The complexity of weighted Boolean \#CSP with mixed signs
- Towards a dichotomy theorem for the counting constraint satisfaction problem
- Finiteness theorems for abelian varieties over number fields.
- Hilbert's irreducibility theorem for prime degree and general polynomials
- Identities for circuit partition polynomials, with applications to the Tutte polynomial
- New results for the Martin polynomial
- Holographic reduction, interpolation and hardness
- Holographic algorithms by Fibonacci gates
- From Holant to \#CSP and back: dichotomy for Holant\(^{c}\) problems
- The complexity of planar Boolean \#CSP with complex weights
- Valiant's holant theorem and matchgate tensors
- The complexity of partition functions
- Gadgets and anti-gadgets leading to a complexity dichotomy
- On the complexity of #CSP
- Computational Complexity of Holant Problems
- Holant Problems for Regular Graphs with Complex Edge Functions
- Quantum Circuits That Can Be Simulated Classically in Polynomial Time
- Tensor rank is NP-complete
- Le Polynôme De Martin D'un Graphe Eulerien
- Holographic Algorithms
- A dichotomy theorem for constraint satisfaction problems on a 3-element set
- On Tractable Exponential Sums
- Simulating Quantum Computation by Contracting Tensor Networks
- The Complexity of Weighted Boolean #CSP
- The NP-Completeness of Edge-Coloring
- Tensor Geometry
- A quantitative version of Runge's theorem on diophantine equations
- The Computational Structure of Monotone Monadic SNP and Constraint Satisfaction: A Study through Datalog and Group Theory
- Codes on graphs: normal realizations
- NP completeness of finding the chromatic index of regular graphs
- Holant problems and counting CSP
- A Complexity Dichotomy for Partition Functions with Mixed Signs
- The complexity of the counting constraint satisfaction problem
- Complexity of counting CSP with complex weights
- The Computational Complexity of Tutte Invariants for Planar Graphs
- A complete dichotomy rises from the capture of vanishing signatures
- Holographic Algorithms with Matchgates Capture Precisely Tractable Planar #CSP
- Dichotomy for Holant Problems with a Function on Domain Size 3
- Graph Homomorphisms with Complex Values: A Dichotomy Theorem