OATAO - Open Archive Toulouse Archive Ouverte Open Access Week

Binary Constraint Satisfaction Problems Defined by Excluded Topological Minors

Cohen, David and Cooper, Martin and Jeavons, Peter and Zivny, Stanislav Binary Constraint Satisfaction Problems Defined by Excluded Topological Minors. (2019) Information and Computation, 264. 12-31. ISSN 0890-5401

(Document in English)

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

Official URL: https://doi.org/10.1016/j.ic.2018.09.013


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 binary CSP instance can be presented as a labelled graph encoding both the forms of the constraints and where they are imposed. We consider subproblems defined by restricting the allowed form of this graph. One type 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 classes defined by language restrictions, or the well-known structural property of acyclicity. In this paper we extend the notion of pattern and introduce the notion of a topological minor of a binary CSP instance. By forbidding certain extended patterns from occurring as sub-patterns or as topological minors we obtain a compact mechanism for expressing all known tractable subproblems of the binary CSP defined by language or structural restrictions. We are also able to define several novel hybrid tractable classes, including new generalisations of the class of acyclic instances.

Item Type:Article
Audience (journal):International peer-reviewed journal
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 > Royal Holloway University of London - RHUL (UNITED KINGDOM)
Other partners > University of Oxford (UNITED KINGDOM)
Laboratory name:
Deposited On:12 Mar 2020 15:03

Repository Staff Only: item control page