Approximating partition functions of bounded-degree Boolean counting Constraint Satisfaction Problems
<p>We study the complexity of #CSP∆(Γ), which is the problem of counting satisfying assignments to CSP instances with constraints from Γ and whose variables can appear at most ∆ times. Our main result shows that: (i) if every function in Γ is affine, then #CSP∆(&a...
| Main Authors: | , , |
|---|---|
| Format: | Journal article |
| Language: | English |
| Published: |
Elsevier
2020
|
| _version_ | 1797099606076555264 |
|---|---|
| author | Galanis, A Goldberg, L Yang, K |
| author_facet | Galanis, A Goldberg, L Yang, K |
| author_sort | Galanis, A |
| collection | OXFORD |
| description | <p>We study the complexity of #CSP∆(Γ), which is the problem of counting satisfying assignments to CSP instances with constraints from Γ and whose variables can appear at most ∆ times. Our main result shows that: (i) if every function in Γ is affine, then #CSP∆(Γ) is in FP for all ∆, (ii) otherwise, if every function in Γ is in a class called IM2, then for large ∆, #CSP∆(Γ) is equivalent under approximation-preserving reductions to the problem of counting independent sets in bipartite graphs, (iii) otherwise, for large ∆, it is NP-hard to approximate #CSP∆(Γ), even within an exponential factor.</p> |
| first_indexed | 2024-03-07T05:26:03Z |
| format | Journal article |
| id | oxford-uuid:e097fd19-985e-41e1-afdf-11c9d8b17380 |
| institution | University of Oxford |
| language | English |
| last_indexed | 2024-03-07T05:26:03Z |
| publishDate | 2020 |
| publisher | Elsevier |
| record_format | dspace |
| spelling | oxford-uuid:e097fd19-985e-41e1-afdf-11c9d8b173802022-03-27T09:48:26ZApproximating partition functions of bounded-degree Boolean counting Constraint Satisfaction ProblemsJournal articlehttp://purl.org/coar/resource_type/c_dcae04bcuuid:e097fd19-985e-41e1-afdf-11c9d8b17380EnglishSymplectic ElementsElsevier2020Galanis, AGoldberg, LYang, K<p>We study the complexity of #CSP∆(Γ), which is the problem of counting satisfying assignments to CSP instances with constraints from Γ and whose variables can appear at most ∆ times. Our main result shows that: (i) if every function in Γ is affine, then #CSP∆(Γ) is in FP for all ∆, (ii) otherwise, if every function in Γ is in a class called IM2, then for large ∆, #CSP∆(Γ) is equivalent under approximation-preserving reductions to the problem of counting independent sets in bipartite graphs, (iii) otherwise, for large ∆, it is NP-hard to approximate #CSP∆(Γ), even within an exponential factor.</p> |
| spellingShingle | Galanis, A Goldberg, L Yang, K Approximating partition functions of bounded-degree Boolean counting Constraint Satisfaction Problems |
| title | Approximating partition functions of bounded-degree Boolean counting Constraint Satisfaction Problems |
| title_full | Approximating partition functions of bounded-degree Boolean counting Constraint Satisfaction Problems |
| title_fullStr | Approximating partition functions of bounded-degree Boolean counting Constraint Satisfaction Problems |
| title_full_unstemmed | Approximating partition functions of bounded-degree Boolean counting Constraint Satisfaction Problems |
| title_short | Approximating partition functions of bounded-degree Boolean counting Constraint Satisfaction Problems |
| title_sort | approximating partition functions of bounded degree boolean counting constraint satisfaction problems |
| work_keys_str_mv | AT galanisa approximatingpartitionfunctionsofboundeddegreebooleancountingconstraintsatisfactionproblems AT goldbergl approximatingpartitionfunctionsofboundeddegreebooleancountingconstraintsatisfactionproblems AT yangk approximatingpartitionfunctionsofboundeddegreebooleancountingconstraintsatisfactionproblems |