Dichotomy for Holant* problems with a function on domain size 3

DOI10.1137/1.9781611973105.93MaRDI QIDQ5741802zbMATH OpenOpenAlexFDO

Authors Jin-Yi Cai, Pinyan Lu, Mingji Xia

Publication date 15 May 2019

Published in Proceedings of the Twenty-Fourth Annual ACM-SIAM Symposium on Discrete Algorithms (Search for Journal in Brave)

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

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Combinatorics in computer science (68R05) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Nonnumerical algorithms (68W05)

Abstract: Holant problems are a general framework to study the algorithmic complexity of counting problems. Both counting constraint satisfaction problems and graph homomorphisms are special cases. All previous results of Holant problems are over the Boolean domain. In this paper, we give the first dichotomy theorem for Holant problems for domain size $>2$. We discover unexpected tractable families of counting problems, by giving new polynomial time algorithms. This paper also initiates holographic reductions in domains of size $>2$. This is our main algorithmic technique, and is used for both tractable families and hardness reductions. The dichotomy theorem is the following: For any complex-valued symmetric function $$ with arity 3 on domain size 3, we give an explicit criterion on $$, such that if $$ satisfies the criterion then the problem $$ is computable in polynomial time, otherwise $$ is #P-hard.

Recommendations

• Dichotomy for Holant* problems of Boolean domain
• Dichotomy for Holant\(^\ast\) problems on the Boolean domain
• Computational complexity of Holant problems
• Holant problems and counting CSP
• From Holant to \#CSP and back: dichotomy for Holant\(^{c}\) problems

Cited in

(13)

• Dichotomy for Holant* problems of Boolean domain
• Restricted Holant dichotomy on domain sizes 3 and 4
• Holographic Algorithm with Matchgates Is Universal for Planar \#CSP over Boolean Domain
• Restricted Holant dichotomy on domains 3 and 4
• Zeros of Holant problems: locations and algorithms
• Polynomial-time solvable \(\#\)CSP problems via algebraic models and Pfaffian circuits
• Dichotomy for Holant\(^\ast\) problems on the Boolean domain
• Nonnegative weighted \#CSP: an effective complexity dichotomy
• FKT is not universal -- a planar holant dichotomy for symmetric constraints
• The complexity of counting \(\mathrm{CSP}^d\)
• The complexity of counting edge colorings and a dichotomy for some higher domain Holant problems
• On the Complexity of Holant Problems
• Zeros and approximations of holant polynomials on the complex plane

This page was built for publication: Dichotomy for Holant* problems with a function on domain size 3

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