The power of arc consistency for CSPs defined by partially-ordered forbidden patterns
Characterising tractable fragments of the constraint satisfaction problem (CSP) is an important challenge in theoretical computer science and artificial intelligence. Forbidding patterns (generic subinstances) provides a means of defining CSP fragments which are neither exclusively language-based no...
| Main Authors: | , |
|---|---|
| Format: | Conference item |
| Published: |
Association for Computing Machinery
2016
|
| _version_ | 1826291662065762304 |
|---|---|
| author | Cooper, M Zivny, S |
| author_facet | Cooper, M Zivny, S |
| author_sort | Cooper, M |
| collection | OXFORD |
| description | Characterising tractable fragments of the constraint satisfaction problem (CSP) is an important challenge in theoretical computer science and artificial intelligence. Forbidding patterns (generic subinstances) provides a means of defining CSP fragments which are neither exclusively language-based nor exclusively structure-based. It is known that the class of binary CSP instances in which the broken-triangle pattern (BTP) does not occur, a class which includes all tree-structured instances, are decided by arc consistency (AC), a ubiquitous reduction operation in constraint solvers. We provide a characterisation of irreducible partially-ordered forbidden patterns which have this AC-solvability property. It turns out that BTP is just one of five such AC-solvable patterns. The four other patterns allow us to exhibit new tractable classes. |
| first_indexed | 2024-03-07T03:02:46Z |
| format | Conference item |
| id | oxford-uuid:b183e6e5-7af3-49d7-883e-dce2f5cd5f0d |
| institution | University of Oxford |
| last_indexed | 2024-03-07T03:02:46Z |
| publishDate | 2016 |
| publisher | Association for Computing Machinery |
| record_format | dspace |
| spelling | oxford-uuid:b183e6e5-7af3-49d7-883e-dce2f5cd5f0d2022-03-27T04:04:36ZThe power of arc consistency for CSPs defined by partially-ordered forbidden patternsConference itemhttp://purl.org/coar/resource_type/c_5794uuid:b183e6e5-7af3-49d7-883e-dce2f5cd5f0dSymplectic Elements at OxfordAssociation for Computing Machinery2016Cooper, MZivny, SCharacterising tractable fragments of the constraint satisfaction problem (CSP) is an important challenge in theoretical computer science and artificial intelligence. Forbidding patterns (generic subinstances) provides a means of defining CSP fragments which are neither exclusively language-based nor exclusively structure-based. It is known that the class of binary CSP instances in which the broken-triangle pattern (BTP) does not occur, a class which includes all tree-structured instances, are decided by arc consistency (AC), a ubiquitous reduction operation in constraint solvers. We provide a characterisation of irreducible partially-ordered forbidden patterns which have this AC-solvability property. It turns out that BTP is just one of five such AC-solvable patterns. The four other patterns allow us to exhibit new tractable classes. |
| spellingShingle | Cooper, M Zivny, S The power of arc consistency for CSPs defined by partially-ordered forbidden patterns |
| title | The power of arc consistency for CSPs defined by partially-ordered forbidden patterns |
| title_full | The power of arc consistency for CSPs defined by partially-ordered forbidden patterns |
| title_fullStr | The power of arc consistency for CSPs defined by partially-ordered forbidden patterns |
| title_full_unstemmed | The power of arc consistency for CSPs defined by partially-ordered forbidden patterns |
| title_short | The power of arc consistency for CSPs defined by partially-ordered forbidden patterns |
| title_sort | power of arc consistency for csps defined by partially ordered forbidden patterns |
| work_keys_str_mv | AT cooperm thepowerofarcconsistencyforcspsdefinedbypartiallyorderedforbiddenpatterns AT zivnys thepowerofarcconsistencyforcspsdefinedbypartiallyorderedforbiddenpatterns AT cooperm powerofarcconsistencyforcspsdefinedbypartiallyorderedforbiddenpatterns AT zivnys powerofarcconsistencyforcspsdefinedbypartiallyorderedforbiddenpatterns |