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

DOI10.1186/S40687-016-0067-8zbMATH Open1344.05060arXiv1404.4020OpenAlexW2412274288WikidataQ59474470 ScholiaQ59474470MaRDI QIDQ313398FDOQ313398

Heng Guo, Tyson Williams, Jin-Yi Cai

Publication date: 9 September 2016

Published in: Research in the Mathematical Sciences (Search for Journal in Brave)

Abstract: We show that an effective version of Siegel's Theorem on finiteness of integer solutions and an application of elementary Galois theory are key ingredients in a complexity classification of some Holant problems. These Holant problems, denoted by Holant(f), are defined by a symmetric ternary function f that is invariant under any permutation of the k >= 3 domain elements. We prove that Holant(f) exhibits a complexity dichotomy. This dichotomy holds even when restricted to planar graphs. A special case of this result is that counting edge k-colorings is #P-hard over planar 3-regular graphs for k >= 3. In fact, we prove that counting edge k-colorings is #P-hard over planar r-regular graphs for all k >= r >= 3. The problem is polynomial-time computable in all other parameter settings. The proof of the dichotomy theorem for Holant(f) depends on the fact that a specific polynomial p(x,y) has an explicitly listed finite set of integer solutions, and the determination of the Galois groups of some specific polynomials. In the process, we also encounter the Tutte polynomial, medial graphs, Eulerian partitions, Puiseux series, and a certain lattice condition on the (logarithm of) the roots of polynomials.

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

Recommendations

• Holant problems for 3-regular graphs with complex edge functions
• Holant problems for regular graphs with complex edge functions
• A Dichotomy for k-Regular Graphs with {0, 1}-Vertex Assignments and Real Edge Functions
• Computational complexity of Holant problems
• The complexity of counting edge colorings for simple graphs

zbMATH Keywords

Tutte polynomialEulerian partitionsmedial graphsPuiseux series

Mathematics Subject Classification ID

Graph polynomials (05C31) Planar graphs; geometric and topological aspects of graph theory (05C10) Coloring of graphs and hypergraphs (05C15) Separable extensions, Galois theory (12F10)

Cites Work

• Finiteness theorems for abelian varieties over number fields.
• Title not available (Why is that?)
• Counting graph homomorphisms
• Tensor Geometry
• Title not available (Why is that?)
• Holographic algorithms by Fibonacci gates
• From Holant to \#CSP and back: dichotomy for Holant\(^{c}\) problems
• The complexity of partition functions
• On the complexity of \#CSP
• Title not available (Why is that?)
• Holant Problems for Regular Graphs with Complex Edge Functions
• Holographic Algorithms
• A dichotomy theorem for constraint satisfaction problems on a 3-element set
• The Complexity of Weighted Boolean #CSP
• The NP-Completeness of Edge-Coloring
• The Computational Structure of Monotone Monadic SNP and Constraint Satisfaction: A Study through Datalog and Group Theory
• Holant problems and counting CSP
• A Complexity Dichotomy for Partition Functions with Mixed Signs
• The complexity of the counting constraint satisfaction problem
• 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
• Graph homomorphisms with complex values: a dichotomy theorem
• The complexity of weighted Boolean \#CSP with mixed signs
• Towards a dichotomy theorem for the counting constraint satisfaction problem
• Title not available (Why is that?)
• Complexity of counting CSP with complex weights
• Quantum Circuits That Can Be Simulated Classically in Polynomial Time
• Title not available (Why is that?)
• NP completeness of finding the chromatic index of regular graphs
• Title not available (Why is that?)
• Title not available (Why is that?)
• Tensor rank is NP-complete
• 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
• The complexity of planar Boolean \#CSP with complex weights
• Valiant's holant theorem and matchgate tensors
• Gadgets and anti-gadgets leading to a complexity dichotomy
• Computational Complexity of Holant Problems
• Le Polynôme De Martin D'un Graphe Eulerien
• On Tractable Exponential Sums
• Simulating Quantum Computation by Contracting Tensor Networks
• The complexity of complex weighted Boolean \#CSP
• A quantitative version of Runge's theorem on diophantine equations
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Codes on graphs: normal realizations
• Title not available (Why is that?)
• Dichotomy for Holant Problems with a Function on Domain Size 3
• Spin systems on \(k\)-regular graphs with complex edge functions

Cited In (5)

• Zeros and approximations of holant polynomials on the complex plane
• The complexity of counting edge colorings for simple graphs
• Holographic Algorithm with Matchgates Is Universal for Planar \#CSP over Boolean Domain
• A Markov chain on the solution space of edge colorings of bipartite graphs
• On the complexity of generalized chromatic polynomials

This page was built for publication: The complexity of counting edge colorings and a dichotomy for some higher domain Holant problems

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