OATAO - Open Archive Toulouse Archive Ouverte Open Access Week

Tractable Classes of Binary CSPs Defined by Excluded Topological Minors

Cohen, David A. and Cooper, Martin C. and Jeavons, Peter G. and Zivny, Stanislav Tractable Classes of Binary CSPs Defined by Excluded Topological Minors. (2015) In: 24th International Joint Conference on Artificial Intelligence (IJCAI 2015), 25 July 2015 - 31 July 2015 (Buenos Aires, Argentina).

(Document in English)

PDF (Author's version) - Requires a PDF viewer such as GSview, Xpdf or Adobe Acrobat Reader

Official URL: http://dl.acm.org/citation.cfm?id=2832519


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.

Item Type:Conference or Workshop Item (Paper)
Additional Information:Thanks to ACM editor. The definitive version is available at http://dl.acm.org This papers appears in IJCAI'15 Proceedings ISBN: 978-1-57735-738-4. The original PDF is available at: http://dl.acm.org/citation.cfm?id=2832519
HAL Id:hal-04079418
Audience (conference):International conference proceedings
Uncontrolled Keywords:
Institution:French research institutions > Centre National de la Recherche Scientifique - CNRS (FRANCE)
Université de Toulouse > Institut National Polytechnique de Toulouse - Toulouse INP (FRANCE)
Université de Toulouse > Université Toulouse III - Paul Sabatier - UT3 (FRANCE)
Université de Toulouse > Université Toulouse - Jean Jaurès - UT2J (FRANCE)
Université de Toulouse > Université Toulouse 1 Capitole - UT1 (FRANCE)
Other partners > University of London (UNITED KINGDOM)
Other partners > University of Oxford (UNITED KINGDOM)
Laboratory name:
Deposited On:13 Sep 2016 14:45

Repository Staff Only: item control page