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

DOI10.1186/S40687-016-0067-8MaRDI QIDQ313398zbMATH OpenOpenAlexWikidataFDO

Authors Jin-Yi Cai, Heng Guo, Tyson Williams

Publication date 9 September 2016

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

Copyright license Creative Commons Attribution 4.0 International

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

zbMATH Keywords

Eulerian partitionsmedial graphsPuiseux seriesTutte polynomial

Mathematics Subject Classification ID

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

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.

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

Cites work

• A complete dichotomy rises from the capture of vanishing signatures (extended abstract)
• A Complexity Dichotomy for Partition Functions with Mixed Signs
• A dichotomy theorem for constraint satisfaction problems on a 3-element set
• A quantitative version of Runge's theorem on diophantine equations
• Codes on graphs: normal realizations
• Complexity of counting CSP with complex weights
• Computational complexity of Holant problems
• Counting graph homomorphisms
• Dichotomy for Holant* problems with a function on domain size 3
• Finiteness theorems for abelian varieties over number fields.
• From Holant to \#CSP and back: dichotomy for Holant\(^{c}\) problems
• Gadgets and anti-gadgets leading to a complexity dichotomy
• Graph edge coloring. Vizing's theorem and Goldberg's conjecture
• Graph homomorphisms with complex values: a dichotomy theorem
• Hilbert's irreducibility theorem for prime degree and general polynomials
• Holant problems and counting CSP
• Holant problems for regular graphs with complex edge functions
• Holographic Algorithms
• Holographic algorithms by Fibonacci gates
• Holographic algorithms with matchgates capture precisely tractable planar \#CSP
• Holographic reduction, interpolation and hardness
• scientific article; zbMATH DE number 437298 (Why is no real title available?)
• scientific article; zbMATH DE number 3887879 (Why is no real title available?)
• scientific article; zbMATH DE number 67324 (Why is no real title available?)
• scientific article; zbMATH DE number 3517311 (Why is no real title available?)
• scientific article; zbMATH DE number 3438977 (Why is no real title available?)
• scientific article; zbMATH DE number 1545676 (Why is no real title available?)
• scientific article; zbMATH DE number 1445310 (Why is no real title available?)
• scientific article; zbMATH DE number 3273761 (Why is no real title available?)
• scientific article; zbMATH DE number 3424129 (Why is no real title available?)
• Identities for circuit partition polynomials, with applications to the Tutte polynomial
• Le Polynôme De Martin D'un Graphe Eulerien
• New results for the Martin polynomial
• NP completeness of finding the chromatic index of regular graphs
• On the complexity of \#CSP
• On tractable exponential sums
• Quantum Circuits That Can Be Simulated Classically in Polynomial Time
• Simulating Quantum Computation by Contracting Tensor Networks
• Spin systems on k-regular graphs with complex edge functions
• Tensor Geometry
• Tensor rank is NP-complete
• The complexity of complex weighted Boolean \#CSP
• The complexity of partition functions
• The complexity of the counting constraint satisfaction problem
• The complexity of weighted Boolean \#CSP modulo \(k\)
• The complexity of weighted Boolean \#CSP with mixed signs
• The Complexity of Weighted Boolean #CSP
• The Computational Complexity of Tutte Invariants for Planar Graphs
• The Computational Structure of Monotone Monadic SNP and Constraint Satisfaction: A Study through Datalog and Group Theory
• The NP-Completeness of Edge-Coloring
• Towards a dichotomy theorem for the counting constraint satisfaction problem
• Valiant's holant theorem and matchgate tensors

Cited in

(7)

• Zeros and approximations of holant polynomials on the complex plane
• The complexity of counting edge colorings for simple graphs
• A Markov chain on the solution space of edge colorings of bipartite graphs
• Holant problems for 3-regular graphs with complex edge functions
• Holographic Algorithm with Matchgates Is Universal for Planar \#CSP over Boolean Domain
• On the complexity of generalized chromatic polynomials
• Packing dimers to maximum occupancy under soft-core constraints

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)