Semantic width and the fixed-parameter tractability of constraint satisfaction problems
Constraint satisfaction problems (CSPs) are an important formal framework for the uniform treatment of various prominent AI tasks, e.g., coloring or scheduling problems. Solving CSPs is, in general, known to be NP-complete and fixed-parameter intractable when parameterized by their constraint scopes...
| Main Authors: | , , , |
|---|---|
| Format: | Conference item |
| Language: | English |
| Published: |
International Joint Conferences on Artificial Intelligence Organization
2020
|
| _version_ | 1797112638939856896 |
|---|---|
| author | Chen, H Gottlob, G Lanzinger, M Pichler, R |
| author_facet | Chen, H Gottlob, G Lanzinger, M Pichler, R |
| author_sort | Chen, H |
| collection | OXFORD |
| description | Constraint satisfaction problems (CSPs) are an important formal framework for the uniform treatment of various prominent AI tasks, e.g., coloring or scheduling problems. Solving CSPs is, in general, known to be NP-complete and fixed-parameter intractable when parameterized by their constraint scopes. We give a characterization of those classes of CSPs for which the problem becomes fixed-parameter tractable. Our characterization significantly increases the utility of the CSP framework by making it possible to decide the fixed-parameter tractability of problems via their CSP formulations. We further extend our characterization to the evaluation of unions of conjunctive queries, a fundamental problem in databases. Furthermore, we provide some new insight on the frontier of PTIME solvability of CSPs. In particular, we observe that bounded fractional hypertree width is more general than bounded hypertree width only for classes that exhibit a certain type of exponential growth. The presented work resolves a long-standing open problem and yields powerful new tools for complexity research in AI and database theory. |
| first_indexed | 2024-03-07T08:28:20Z |
| format | Conference item |
| id | oxford-uuid:e00c203e-ce47-401a-bbd9-eef371dd3f8f |
| institution | University of Oxford |
| language | English |
| last_indexed | 2024-03-07T08:28:20Z |
| publishDate | 2020 |
| publisher | International Joint Conferences on Artificial Intelligence Organization |
| record_format | dspace |
| spelling | oxford-uuid:e00c203e-ce47-401a-bbd9-eef371dd3f8f2024-02-21T13:09:17ZSemantic width and the fixed-parameter tractability of constraint satisfaction problemsConference itemhttp://purl.org/coar/resource_type/c_5794uuid:e00c203e-ce47-401a-bbd9-eef371dd3f8fEnglishSymplectic ElementsInternational Joint Conferences on Artificial Intelligence Organization2020Chen, HGottlob, GLanzinger, MPichler, RConstraint satisfaction problems (CSPs) are an important formal framework for the uniform treatment of various prominent AI tasks, e.g., coloring or scheduling problems. Solving CSPs is, in general, known to be NP-complete and fixed-parameter intractable when parameterized by their constraint scopes. We give a characterization of those classes of CSPs for which the problem becomes fixed-parameter tractable. Our characterization significantly increases the utility of the CSP framework by making it possible to decide the fixed-parameter tractability of problems via their CSP formulations. We further extend our characterization to the evaluation of unions of conjunctive queries, a fundamental problem in databases. Furthermore, we provide some new insight on the frontier of PTIME solvability of CSPs. In particular, we observe that bounded fractional hypertree width is more general than bounded hypertree width only for classes that exhibit a certain type of exponential growth. The presented work resolves a long-standing open problem and yields powerful new tools for complexity research in AI and database theory. |
| spellingShingle | Chen, H Gottlob, G Lanzinger, M Pichler, R Semantic width and the fixed-parameter tractability of constraint satisfaction problems |
| title | Semantic width and the fixed-parameter tractability of constraint satisfaction problems |
| title_full | Semantic width and the fixed-parameter tractability of constraint satisfaction problems |
| title_fullStr | Semantic width and the fixed-parameter tractability of constraint satisfaction problems |
| title_full_unstemmed | Semantic width and the fixed-parameter tractability of constraint satisfaction problems |
| title_short | Semantic width and the fixed-parameter tractability of constraint satisfaction problems |
| title_sort | semantic width and the fixed parameter tractability of constraint satisfaction problems |
| work_keys_str_mv | AT chenh semanticwidthandthefixedparametertractabilityofconstraintsatisfactionproblems AT gottlobg semanticwidthandthefixedparametertractabilityofconstraintsatisfactionproblems AT lanzingerm semanticwidthandthefixedparametertractabilityofconstraintsatisfactionproblems AT pichlerr semanticwidthandthefixedparametertractabilityofconstraintsatisfactionproblems |