Approximate counting CSP seen from the other side
In this paper we study the complexity of counting Constraint Satisfaction Problems (CSPs) of the form #CSP(C,-), in which the goal is, given a relational structure A from a class C of structures and an arbitrary structure B, to find the number of homomorphisms from A to B. Flum and Grohe showed that...
| Main Authors: | , |
|---|---|
| Format: | Conference item |
| Published: |
Schloss Dagstuhl - Leibniz-Zentrum für Informatik
2019
|
| _version_ | 1797087495964327936 |
|---|---|
| author | Bulatov, A Zivny, S |
| author_facet | Bulatov, A Zivny, S |
| author_sort | Bulatov, A |
| collection | OXFORD |
| description | In this paper we study the complexity of counting Constraint Satisfaction Problems (CSPs) of the form #CSP(C,-), in which the goal is, given a relational structure A from a class C of structures and an arbitrary structure B, to find the number of homomorphisms from A to B. Flum and Grohe showed that #CSP(C,-) is solvable in polynomial time if C has bounded treewidth [FOCS'02]. Building on the work of Grohe [JACM'07] on decision CSPs, Dalmau and Jonsson then showed that, if C is a recursively enumerable class of relational structures of bounded arity, then assuming FPT != #W[1], there are no other cases of #CSP(C,-) solvable exactly in polynomial time (or even fixed-parameter time) [TCS'04]. We show that, assuming FPT != W[1] (under randomised parametrised reductions) and for C satisfying certain general conditions, #CSP(C,-) is not solvable even approximately for C of unbounded treewidth; that is, there is no fixed parameter tractable (and thus also not fully polynomial) randomised approximation scheme for #CSP(C,-). In particular, our condition generalises the case when C is closed under taking minors. |
| first_indexed | 2024-03-07T02:36:28Z |
| format | Conference item |
| id | oxford-uuid:a8f43265-d568-416f-8546-175b2ad80922 |
| institution | University of Oxford |
| last_indexed | 2024-03-07T02:36:28Z |
| publishDate | 2019 |
| publisher | Schloss Dagstuhl - Leibniz-Zentrum für Informatik |
| record_format | dspace |
| spelling | oxford-uuid:a8f43265-d568-416f-8546-175b2ad809222022-03-27T03:05:08ZApproximate counting CSP seen from the other sideConference itemhttp://purl.org/coar/resource_type/c_5794uuid:a8f43265-d568-416f-8546-175b2ad80922Symplectic Elements at OxfordSchloss Dagstuhl - Leibniz-Zentrum für Informatik2019Bulatov, AZivny, SIn this paper we study the complexity of counting Constraint Satisfaction Problems (CSPs) of the form #CSP(C,-), in which the goal is, given a relational structure A from a class C of structures and an arbitrary structure B, to find the number of homomorphisms from A to B. Flum and Grohe showed that #CSP(C,-) is solvable in polynomial time if C has bounded treewidth [FOCS'02]. Building on the work of Grohe [JACM'07] on decision CSPs, Dalmau and Jonsson then showed that, if C is a recursively enumerable class of relational structures of bounded arity, then assuming FPT != #W[1], there are no other cases of #CSP(C,-) solvable exactly in polynomial time (or even fixed-parameter time) [TCS'04]. We show that, assuming FPT != W[1] (under randomised parametrised reductions) and for C satisfying certain general conditions, #CSP(C,-) is not solvable even approximately for C of unbounded treewidth; that is, there is no fixed parameter tractable (and thus also not fully polynomial) randomised approximation scheme for #CSP(C,-). In particular, our condition generalises the case when C is closed under taking minors. |
| spellingShingle | Bulatov, A Zivny, S Approximate counting CSP seen from the other side |
| title | Approximate counting CSP seen from the other side |
| title_full | Approximate counting CSP seen from the other side |
| title_fullStr | Approximate counting CSP seen from the other side |
| title_full_unstemmed | Approximate counting CSP seen from the other side |
| title_short | Approximate counting CSP seen from the other side |
| title_sort | approximate counting csp seen from the other side |
| work_keys_str_mv | AT bulatova approximatecountingcspseenfromtheotherside AT zivnys approximatecountingcspseenfromtheotherside |