Tractable classes of binary CSPs defined by excluded topological minors

David Cohen, Martin Cooper, Peter Jeavons, Stanislav Zivny

Research output: Contribution to conferencePaperpeer-review

45 Downloads (Pure)


The binary Constraint Satisfaction Problem (CSP)is to decide whether there exists an assignment to aset of variables which satisfies specified constraintsbetween pairs of variables. A CSP instance canbe presented as a labelled graph (called the microstructure)encoding both the forms of the constraintsand where they are imposed. We considersubproblems defined by restricting the allowedform of the microstructure. One form ofrestriction that has previously been considered isto forbid certain specified substructures (patterns).This captures some tractable classes of the CSP,but does not capture the well-known property ofacyclicity. In this paper we introduce the notionof a topological minor of a binary CSP instance.By forbidding certain patterns as topological minorswe obtain a compact mechanism for expressingseveral novel tractable classes, including newgeneralisations of the class of acyclic instances.
Original languageEnglish
Number of pages7
Publication statusPublished - 25 Jul 2015
EventIJCAI - Beijing, China
Duration: 3 Aug 20139 Aug 2013



Cite this