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 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.