Tractable classes of binary CSPs defined by excluded topological minors
The binary Constraint Satisfaction Problem (CSP) is to decide whether there exists an assignment to a set of variables which satisfies specified constraints between pairs of variables. A CSP instance can be presented as a labelled graph (called the microstructure) encoding both the forms of the cons...
| Main Authors: | , , , |
|---|---|
| Other Authors: | |
| Format: | Conference item |
| Language: | English |
| Published: |
International Joint Conferences on Artificial Intelligence
2015
|
| _version_ | 1826279638704324608 |
|---|---|
| author | Cohen, D Cooper, M Jeavons, P Živný, S |
| author2 | International Joint Conference on Artificial Intelligence |
| author_facet | International Joint Conference on Artificial Intelligence Cohen, D Cooper, M Jeavons, P Živný, S |
| author_sort | Cohen, D |
| collection | OXFORD |
| description | The binary Constraint Satisfaction Problem (CSP) is to decide whether there exists an assignment to a set of variables which satisfies specified constraints between pairs of variables. A CSP instance can be presented as a labelled graph (called the microstructure) encoding both the forms of the constraints and where they are imposed. We consider subproblems defined by restricting the allowed form of the microstructure. One form of restriction that has previously been considered is to forbid certain specified substructures (patterns). This captures some tractable classes of the CSP, but does not capture the well-known property of acyclicity. In this paper we introduce the notion of a topological minor of a binary CSP instance. By forbidding certain patterns as topological minors we obtain a compact mechanism for expressing several novel tractable classes, including new generalisations of the class of acyclic instances. |
| first_indexed | 2024-03-07T00:01:45Z |
| format | Conference item |
| id | oxford-uuid:76330017-217c-4713-a8e0-c38e59ba4d74 |
| institution | University of Oxford |
| language | English |
| last_indexed | 2024-03-07T00:01:45Z |
| publishDate | 2015 |
| publisher | International Joint Conferences on Artificial Intelligence |
| record_format | dspace |
| spelling | oxford-uuid:76330017-217c-4713-a8e0-c38e59ba4d742022-03-26T20:14:06ZTractable classes of binary CSPs defined by excluded topological minorsConference itemhttp://purl.org/coar/resource_type/c_5794uuid:76330017-217c-4713-a8e0-c38e59ba4d74EnglishOxford University Research Archive - ValetInternational Joint Conferences on Artificial Intelligence2015Cohen, DCooper, MJeavons, PŽivný, SInternational Joint Conference on Artificial IntelligenceAsociación Argentina de Inteligencia ArtificialThe binary Constraint Satisfaction Problem (CSP) is to decide whether there exists an assignment to a set of variables which satisfies specified constraints between pairs of variables. A CSP instance can be presented as a labelled graph (called the microstructure) encoding both the forms of the constraints and where they are imposed. We consider subproblems defined by restricting the allowed form of the microstructure. One form of restriction that has previously been considered is to forbid certain specified substructures (patterns). This captures some tractable classes of the CSP, but does not capture the well-known property of acyclicity. In this paper we introduce the notion of a topological minor of a binary CSP instance. By forbidding certain patterns as topological minors we obtain a compact mechanism for expressing several novel tractable classes, including new generalisations of the class of acyclic instances. |
| spellingShingle | Cohen, D Cooper, M Jeavons, P Živný, S Tractable classes of binary CSPs defined by excluded topological minors |
| title | Tractable classes of binary CSPs defined by excluded topological minors |
| title_full | Tractable classes of binary CSPs defined by excluded topological minors |
| title_fullStr | Tractable classes of binary CSPs defined by excluded topological minors |
| title_full_unstemmed | Tractable classes of binary CSPs defined by excluded topological minors |
| title_short | Tractable classes of binary CSPs defined by excluded topological minors |
| title_sort | tractable classes of binary csps defined by excluded topological minors |
| work_keys_str_mv | AT cohend tractableclassesofbinarycspsdefinedbyexcludedtopologicalminors AT cooperm tractableclassesofbinarycspsdefinedbyexcludedtopologicalminors AT jeavonsp tractableclassesofbinarycspsdefinedbyexcludedtopologicalminors AT zivnys tractableclassesofbinarycspsdefinedbyexcludedtopologicalminors |