The complexity of counting edge colorings and a dichotomy for some higher domain Holant problems

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

zbMATH Keywords

Tutte polynomialPuiseux seriesEulerian partitionsmedial graphs

Mathematics Subject Classification ID

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