  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 a finite set of
patterns from occurring as topological minors we obtain a compact mechanism for
expressing novel tractable subproblems of the binary CSP, including new
generalisations of the class of acyclic instances. Forbidding a finite set of
patterns as topological minors also captures all other tractable structural
restrictions of the binary CSP. Moreover, we show that several patterns give
rise to tractable subproblems if forbidden as topological minors but not if
forbidden as sub-patterns. Finally, we introduce the idea of augmented patterns
that allows for the identification of more tractable classes, including all
language restrictions of the binary CSP.
