Approximation complexity of complex-weighted degree-two counting constraint satisfaction problems

DOI10.1016/J.TCS.2011.11.037zbMATH Open1253.68185arXiv1109.5789OpenAlexW1479905431MaRDI QIDQ690466FDOQ690466

Authors: Tomoyuki Yamakami 

Publication date: 27 November 2012

Published in: Theoretical Computer Science (Search for Journal in Brave)

Abstract: Constraint satisfaction problems have been studied in numerous fields with practical and theoretical interests. In recent years, major breakthroughs have been made in a study of counting constraint satisfaction problems (or #CSPs). In particular, a computational complexity classification of bounded-degree #CSPs has been discovered for all degrees except for two, where the "degree" of an input instance is the maximal number of times that each input variable appears in a given set of constraints. Despite the efforts of recent studies, however, a complexity classification of degree-2 #CSPs has eluded from our understandings. This paper challenges this open problem and gives its partial solution by applying two novel proof techniques--T_{2}-constructibility and parametrized symmetrization--which are specifically designed to handle "arbitrary" constraints under randomized approximation-preserving reductions. We partition entire constraints into four sets and we classify the approximation complexity of all degree-2 #CSPs whose constraints are drawn from two of the four sets into two categories: problems computable in polynomial-time or problems that are at least as hard as #SAT. Our proof exploits a close relationship between complex-weighted degree-2 #CSPs and Holant problems, which are a natural generalization of complex-weighted #CSPs.

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

Recommendations

• Approximation complexity of complex-weighted degree-two counting constraint satisfaction problems (extended abstract)
• A dichotomy theorem for the approximate counting of complex-weighted bounded-degree Boolean CSPs
• A trichotomy theorem for the approximate counting of complex-weighted bounded-degree Boolean CSPs
• The complexity of approximating bounded-degree Boolean \(\#\)CSP

zbMATH Keywords

signaturesymmetrizationconstraint satisfaction problembounded degreeholant problemconstructibility\# CSP\# SATAP-reducibility

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) Approximation algorithms (68W25)

Cites Work

• The relative complexity of approximate counting problems
• Holographic Algorithms
• The Complexity of Weighted Boolean #CSP
• The Complexity of Enumeration and Reliability Problems
• Holant problems and counting CSP
• The complexity of satisfiability problems
• An approximation trichotomy for Boolean \#CSP
• Complexity of generalized satisfiability counting problems
• Holographic algorithms: from art to science
• The complexity of approximating bounded-degree Boolean \#CSP
• Signature Theory in Holographic Algorithms
• Expressiveness of matchgates.

Cited In (3)

• Complexity of approximating CSP with balance / hard constraints
• Constant unary constraints and symmetric real-weighted counting constraint satisfaction problems
• Approximation complexity of complex-weighted degree-two counting constraint satisfaction problems (extended abstract)

This page was built for publication: Approximation complexity of complex-weighted degree-two counting constraint satisfaction problems

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