Holant clones and the approximability of conservative holant problems

DOI10.1145/3381425MaRDI QIDQ4987440zbMATH OpenOpenAlexFDO

Authors Miriam Backens, Leslie Ann Goldberg

Publication date 3 May 2021

Published in ACM Transactions on Algorithms (Search for Journal in Brave)

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

zbMATH Keywords

approximate countingcomputational counting problemfunctional cloneholant problem

Mathematics Subject Classification ID

Operations and polynomials in algebraic structures, primal algebras (08A40) Applications of universal algebra in computer science (08A70) Analysis of algorithms and problem complexity (68Q25) Combinatorics in computer science (68R05)

Abstract: We construct a theory of holant clones to capture the notion of expressibility in the holant framework. Their role is analogous to the role played by functional clones in the study of weighted counting Constraint Satisfaction Problems. We explore the landscape of conservative holant clones and determine the situations in which a set $mathcalF$ of functions is "universal in the conservative case", which means that all functions are contained in the holant clone generated by $mathcalF$ together with all unary functions. When $mathcalF$ is not universal in the conservative case, we give concise generating sets for the clone. We demonstrate the usefulness of the holant clone theory by using it to give a complete complexity-theory classification for the problem of approximating the solution to conservative holant problems. We show that approximation is intractable exactly when $mathcalF$ is universal in the conservative case.

Recommendations

• Computational complexity of Holant problems
• The complexity of approximating conservative counting CSPs
• Holant problems and counting CSP
• The complexity of approximating conservative counting CSPs
• From Holant to \#CSP and back: dichotomy for Holant\(^{c}\) problems

Cited in

(9)

• A full dichotomy for \(\mathrm{Holant}^c\), inspired by quantum computation
• Dichotomy result on 3-regular bipartite non-negative functions
• Bipartite 3-regular counting problems with mixed signs
• Dichotomy result on 3-regular bipartite non-negative functions
• Bipartite 3-regular counting problems with mixed signs
• Restricted Holant dichotomy on domains 3 and 4
• Restricted Holant dichotomy on domain sizes 3 and 4
• A combinatorial view of Holant problems on higher domains
• Symmetries and complexity (invited talk)

This page was built for publication: Holant clones and the approximability of conservative holant problems

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