Tractable Classes of Binary CSPs Defined by Excluded Topological Minors

1 Introduction

The binary Constraint Satisfaction Problem (CSP) is to decide whether it is possible to find an assignment to a set of variables which satisfies a specified set of constraints between certain pairs of variables. This paradigm has been applied in diverse application areas such as Artificial Intelligence, Bioinformatics and Operations Research [Rossi et al., 2006].

As the CSP is known to be NP-complete, much theoretical work has been devoted to the identification of tractable subproblems. Important tractable cases have been identified by restricting the set of pairs where the constraints are imposed (sometimes called the constraint structure) [Grohe, 2007; Marx, 2013]. Other tractable cases have been identified by restricting the forms of constraints (sometimes called the constraint language) [Cohen and Jeavons, 2003; Barto and Kozik, 2014]. Work on both of these areas is now very far advanced: a full complexity dichotomy for any structural or language restriction now requires the classification of just one remaining family of languages [Barto and Kozik, 2014].

∗The authors were supported by EPSRC grant EP/L021226/1. Stanislav ˇZivn´y was supported by a Royal Society University Research Fellowship.

Martin C. Cooper

IRIT, Univ. of Toulouse, 31062 Toulouse, France cooper@irit.fr

Peter G. Jeavons & Stanislav ˇZivn´y

Dept. of Computer Science,

Univ. of Oxford, UK peter.jeavons@cs.ox.ac.uk standa.zivny@cs.ox.ac.uk

A CSP instance can be represented as a labelled graph (known as the microstructure), encoding both the constraint structure and the constraint language. By restricting the allowed form of the microstructure it is possible to impose simultaneous restrictions on both the structure and the language of an instance, and hence obtain a more refined collection of subproblems, allowing a more detailed complexity analysis. Currently, very little is known about the complexity of the subproblems obtained by restricting both the structure and the language of the set of instances at the same time.

Following a well-established line of research in graph theory, restrictions on the microstructure of an instance can be defined by considering local "obstructions" or "forbidden patterns". In this paper we introduce the notion of a topological minor of a binary CSP instance. By forbidding certain patterns as topological minors we provide a compact mechanism for expressing several novel tractable classes, including new generalisations of the class of instances with acyclic structure.

2 Definitions

A binary CSP instance requires the assignment of values from some specified finite domain to a finite set of variables {X1, . . . ,Xn}. Each pair of variables, Xi and Xj is constrained by a constraint relation Ri j. A constraint is non-trivial if it is not the Cartesian product of the domains of the two variables. A solution to a binary CSP instance is an assignment s of values to variables, such that, for each constraint Ri j, 〈s(Xi), s(X j )〉 ∈ Ri j

The constraint graph of an instance I is GI = 〈VI,EI〉, where VI = {X1, . . . ,Xn} is the set of variables of I and EI is the set of pairs {Xi,Xj} for which Ri j is non-trivial.

One possible presentation of a binary CSP instance is as a labelled graph whose vertices are the set of possible variable-value assignments. This (labelled) graph is known as the (coloured) microstructure [J´egou, 1993; Angelsmark and Thapper, 2005; Cohen et al., 2006; Salamon and Jeavons, 2008; Cohen et al., 2012; El Mouelhi et al., 2013]. An n-variable binary CSP instance I in this microstructure presentation is an n-partite graph 〈A1, . . . ,An,E +〉, where the ith part Ai corresponds to the set of possible assignments 〈Xi,a〉 to variable Xi and there is an edge in E + between 〈Xi,a〉 ∈ Ai and 〈Xj,b〉 ∈ Aj if and only if (a,b) ∈ Ri j. We refer to individual variable-value assignments, such as 〈Xi,a〉 as points. If X is some variable of the instance we use the notation AX

to represent the set of possible assignments to X. Thus Ai and AXi are synonyms.

An instance I can also be presented as a negative microstructure which is the n-partite labelled graph 〈A1, . . . , An, E -〉, where there is an edge in E - between points p ∈ Ai and q ∈ Aj (for i ̸= j) if and only if there is no edge between p and q in E +.

Patterns and Sub-Patterns: We now generalise the notion of microstructure and negative microstructure to obtain patterns: a pattern is a labelled n-partite graph which has a set of positive edges, E +, and a set of negative edges, E -.

A binary CSP instance can be seen as a special kind of pattern where the parts correspond to the variables of the instance and there is exactly one positive or negative edge between each pair of possible assignments to each pair of distinct variables. Positive edges connect assignments that are allowed by the constraint on the corresponding pair of variables, and negative edges connect assignments that are disallowed by this constraint.

A general pattern P = 〈A1, . . . ,An,E +,E -〉 can in some ways be viewed as a partially specified instance: there may be pairs of points p ∈ Ai,q ∈ Aj (with i ̸= j) such that there is neither a positive edge nor a negative edge between p and q. (However, there can also be both a positive and a negative edge between p and q, see below.) A point is said to be isolated if it does not belong to any edges in E + or E -.

A pattern P′ = 〈A′1 , . . . , A′n, E ′+, E ′-〉 is a homomorphic image of a pattern P = 〈A1, . . . ,An,E +,E -〉 if there exists a surjective mapping f : ⋃n i=1Ai → ⋃n i=1A′i such that

• ∀p,q ∈ ⋃n k=1 Ak, p and q belong to the same part Ai if and only if f (p) and f (q) belong to the same part A′j ,
• ∀i, j ∈ {1, . . . ,n} with i ̸= j, ∀p ∈ Ai, ∀q ∈ Aj: {p,q} ∈ E + ⇒ { f (p), f (q)} ∈ E ′+ and {p,q} ∈ E - ⇒ { f (p), f (q)} ∈E ′-.

Note that forming a homomorphic image of a pattern allows the parts to be renamed, and compatible points within the same part to be merged.

We will say that a pattern P occurs as a sub-pattern of a pattern Q if Q can be transformed into a homomorphic image of P by a sequence of the following substructure operations:

• removal of (positive or negative) edges,
• removal of isolated points, and
• removal of empty parts.

This notion of occurring as a sub-pattern has led to the discovery of several new tractable classes [Cooper et al., 2010; Cohen et al., 2012; Cooper and Escamocher, 2012]: in each case the class is defined by a simple forbidden pattern, i.e., as the set of binary CSP instances in which the given pattern does not occur as a sub-pattern.

Topological Minors We now present a new operation on patterns which allows us to define the notion of a topological minor of a pattern (and hence of a binary CSP instance). This new operation is analogous to the operation of eliminating subdivisions (vertices of degree 2) that is used to define a topological minor of a graph [Diestel, 2010]. However, since patterns contain two kinds of edges, the definition is slightly more complicated.

This new operation, path reduction, will sometimes lead to the introduction of edges in E + ∪E -. Hence, we relax the restriction that E + and E - be disjoint.

In a pattern P = 〈A1, . . . , An, E +, E -〉, we say that two parts Ai,Aj are directly connected if there is at least one (positive or negative) edge {p, q} ∈ E + ∪E - with p ∈ Ai and q ∈ A j .

If Ai,Aj are not directly connected and Ak is directly connected only to Ai and Aj, then the following operation can be performed, which is known as path reduction:

1. ∀p∈Ai, ∀q∈Aj: if ∃r ∈Ak such that {p,r},{r,q}∈E +, then introduce a new positive edge {p, q},
2. ∀p ∈ Ai, ∀q ∈ Aj: if ∃r,s ∈ Ak such that {p,r},{s,q} ∈ E -, then introduce a new negative edge {p,q},
3. remove the part Ak and all edges containing points in Ak.

Positive and negative edges are treated differently in this definition; this is because for p∈Ai and q∈Aj to be part of a solution to the sub-instance on variables Xi,Xj,Xk, the points p and q must both be compatible with some common point r ∈ Ak, whereas p and q may be incompatible if they are each incompatible with some point in Ak, not necessarily the same point. This asymmetry in the definition seems to lead to more useful results.

A pattern P occurs as a topological minor of a pattern Q if Q can be transformed into a homomorphic image of P by a sequence of substructure operations and path reductions.

3 Some basic tractability results

We use the notation CSP SP (P) to represent the set of binary CSP instances in which the pattern P does not occur as a subpattern. We use the notation CSP TM(P) to represent the set of binary CSP instances in which the pattern P does not occur as a topological minor. For each pattern P there are therefore two distinct notions of tractability, defined as follows.

Definition 3.1 A pattern P is sub-pattern tractable if there is a polynomial-time algorithm to solve CSP SP (P). A pattern P is topological-minor tractable if there is a polynomial-time algorithm to solve CSP TM(P).

The following lemma follows directly from the definitions.

Lemma 3.2 If a pattern P is sub-pattern tractable then P is topological-minor tractable.

The two patterns shown in Figure 1(a) and 1(b) are known to be sub-pattern tractable [Cooper and ˇZivn´y, 2012; Escamocher, 2013]. Hence, they are also topological-minor tractable, by Lemma 3.2.

Lemma 3.3 If pattern P occurs as a topological minor in pattern Q, and Q is topological-minor tractable, then P is topological-minor tractable.

Proof: Suppose that P occurs in pattern Q as a topological minor. From the transitivity of the occurrence (as a topological minor) relation, we can deduce that CSP TM(P) ⊆ CSPTM(Q). It follows, directly, that if Q is topological-minor tractable, then P is also topological-minor tractable.

✟

✠

✟

✠

As a simple example, we can deduce from Lemma 3.3 that Figure 1(c) is topological-minor tractable, since Figure 1(c) occurs in Figure 1(b) as a topological minor and we have already seen that Figure 1(b) is topological-minor tractable.

4 Acyclicity and bounded treewidth

One important tractable class of binary CSP instances is the class of instances whose constraint graph is acyclic [Freuder, 1982]. However, this class cannot be defined by a finite set of forbidden sub-patterns, as the following result shows.

Lemma 4.1 The class of acyclic binary CSP instances cannot be characterised by a finite set of forbidden sub-patterns.

Proof: Let T be a finite set of patterns which do not occur in any acyclic CSP instance, and let k be the maximum number of parts in any pattern from T. Consider an instance I with variables {X1, . . . ,Xk+1} and non-trivial constraints between Xi and Xi+1 for i = 1, . . . ,k and between Xk+1 and X1. No pattern from T occurs as a sub-pattern in I, since any subpattern of I with at most k variables is acyclic. Since I is not acyclic we are done.

On the other hand, it is straightforward to characterise the class of acyclic instances by forbidding a single pattern as a topological minor. For any graph G on vertices {v1, . . . , vn}, we can create a corresponding pattern PG with a part Ai for each vertex vi of G and, for each edge e = {vi,vj} of G, a negative edge in PG between points pe ∈ Ai and qe ∈ A j , these points being distinct for each edge e. For example, when G is a 3-cycle, the corresponding pattern PG is shown in Figure 2. Every edge in the constraint graph corresponds to a non-trivial constraint relation, that forbids at least one pair of points. Hence, the pattern PG is a topological minor of a binary CSP instance I if and only if G is a topological minor of the constraint graph of I. Hence forbidding the pattern shown in Figure 2 as a topological minor exactly defines the class of binary CSP instances whose constraint graph is acyclic.

This idea can easily be extended to any of the tractable classes of binary CSP instances defined by imposing any fixed bound on the treewidth of the constraint graph [Freuder, 1985]. The graph minor theorem [Robertson and Seymour, 2004] implies that for any fixed k ≥ 1 there is a finite set Ok of graphs such that the class of graphs of treewidth at most k is precisely the class of graphs excluding all graphs from the set Ok as topological minors [Diestel, 2010]. Consequently, for any k ≥ 1 the class of binary CSP instances of treewidth at most k can be defined by a finite set of patterns that are forbidden as topological minors.

5 Tractability via Tutte decomposition

In this section we will describe a generic scheme for proving tractability of classes of binary CSP instances defined by a forbidden topological minor. We will use this scheme in the proofs of Proposition 6.4 and Theorem 7.1.

If U is a set of vertices of a graph G, we write G[U] for the induced graph on U. We say that 〈U1,U2〉 is a separation of G if G=G[U1]∪G[U2]. The separator of the separation 〈U1,U2〉 is U1 ∩U2 and its order is |U1 ∩U2|. The torso of U1 in the separation 〈U1,U2〉 is obtained from the induced graph G[U1] by adding every edge between the vertices of the separator. A Tutte decomposition of a graph G is a tree T where each node is labelled with a subset of the vertices of G, each arc induces a separation of G of order at most two, and the torso of each node is three-connected, or a cycle, or has at most 2 vertices. Every finite graph has a Tutte decomposition of this kind [Tutte, 1966].

To demonstrate topological-minor tractability for a pattern P we proceed as follows. Let I be an instance in which P does not occur as a topological minor and let GI be its constraint graph. We denote by n the number of variables in I and by d the maximum domain size of any variable in I.

Build a Tutte tree decomposition, T, of GI , and consider any leaf C of T inducing the separation 〈C,R〉 of GI , with separator S. Let IC be the subinstance of I on the variables corresponding to the vertices of C, and let Ct be the torso of C. Suppose that the following two assumptions hold:

• (A1) IC can be solved and its solutions projected onto the separator S in polynomial time; the resulting reduced instance on R will be denoted by Ired .
• (A2) P does not occur in Ired as a topological minor.

Then it follows that a recursive algorithm, which at each step chooses some leaf C of T , and then solves the associated subproblem IC to obtain the reduced instance Ired, will solve the original instance using a polynomial (in n and d) number of calls to the polynomial-time algorithm from (A1).

In the proofs below we will omit the simple cases where the separator S has order less than two, or C contains at most 3 vertices, or the torso of C is a cycle (and hence has treewidth 2 and is solvable in polynomial time). Hence we will assume that C is three-connected and of size greater than three.

Finally, note that if {u,v} is an order 2 separator for some separation 〈C,R〉 of GI then we have the following:

✟

✠

• Any path from a vertex in C to a vertex in R must pass through u or v;
• There must exist some path from u to v in GI [R], which we will denote pathR(u,v).

6 Some topological-minor tractable patterns

Consider the patterns shown in Figure 3. By the classification theorem for patterns with only negative edges given in [Cohen et al., 2012], the class of instances obtained by forbidding the pattern Q as a sub-pattern, CSP SP (Q), is NP-complete. Similarly for pattern P. The pattern E2 cannot occur as a subpattern in a CSP instance, and hence CSP SP (E2) is the class of all instances and so is trivially NP-complete. However, we will show in this section that these three patterns define tractable classes when forbidden as topological minors.

Proposition 6.1 The patterns Q and M, shown in Figure 3, are topological-minor tractable.

Proof: It is known that CSP SP (M) can be solved in polynomial time, since M is a sub-pattern of the pattern shown in Figure 1(a) [Cooper and ˇZivn´y, 2012]. Hence we only need to prove the result for Q.

Consider an instance I in which the pattern Q does not occur as a topological minor, and let GI be the constraint graph of I. Suppose the pattern M occurs as a sub-pattern on the triple of variables (x,y,z) in I, with y being the variable at which the two negative edges meet.

Since Q does not occur as a topological minor in I, it follows that there is no path from x to z in GI that does not pass through y. We can therefore find a tree-decomposition of GI into components in which M does not occur as a sub-pattern and joined at such variables y which we can call articulation variables. Since CSP SP (M) is tractable, any subinstance corresponding to a leaf component can be solved in polynomial time for each possible assignment to the unique articulation variable which joins it to its parent component in the treedecomposition. This leads to the elimination of the leaf component and possible elimination of some values in the domain of this articulation variable. The original instance I can be solved in polynomial time by repeatedly solving subinstances corresponding to leaf components in this way.

Proposition 6.2 The pattern E2, shown in Figure 3, is topological-minor tractable.

Proof: Since the pattern E2 cannot occur as a sub-pattern in any instance, it can only occur as a topological minor if there is at least one path reduction operation. Hence excluding the pattern E2 as a topological minor is equivalent to excluding the pattern in Figure 1(c) as a topological minor. In Section 2 we observed that Figure 1(c) is topological-minor tractable, so it follows that E2 is topological-minor tractable.

Corollary 6.3 All 2-part patterns are topological-minor tractable.

Proof: Let P2 be an arbitrary 2-part pattern. The function which maps all of A1 to a and all of A2 to b is necessarily a homomorphism from P2 to the pattern E2 in Figure 3, since {a, b} is both a negative and a positive edge in E2. By Proposition 6.2 and Lemma 3.3, it follows that P2 is tractable.

Proposition 6.4 The pattern P, shown in Figure 3, is topological-minor tractable.

Proof: The proof uses the generic scheme described in Section 5, so we only need to establish the two assumptions.

(A1) Let M be the pattern consisting of two intersecting negative edges, shown in Figure 3. Suppose that M occurs in IC as a sub-pattern on two disjoint triples of variables (x,y,z) and (x′ ,y′ ,z′ ). As explained in Section 5, we assume thatCt is 3-connected. It follows by Menger's theorem [Dirac, 1966] that there are three disjoint paths from x to x′ in Ct . There must be one of these paths, p, which does not pass through y or y′ . There must be a subpath s of p which begins at x or z and ends at x′ or z′ (or vice versa, i.e., which begins at x′ or z′ and ends at x or z) and which does not pass through any other variables in {x, y, z, x′ , y′ , z′}. Without loss of generality, suppose that s joins x to x′ . But then P occurs as a topological minor on the extended path s + given by z → y → x,s, x′ → y′ → z′ .

But this implies that P occurs as a topological minor in I, since if s + passes by the edge {u,v} in the torso Ct , this edge can be replaced by pathR(u,v) which is a path from u to v in R, whose existence was noted in Section 5. Since this contradicts our initial assumption, we can deduce that M does not occur in IC as a sub-pattern on two disjoint triples.

We can therefore deduce that all pairs of triples of variables (x,y,z), (x′ ,y′ ,z′ ) on which M occurs as a sub-pattern in IC intersect, i.e. {x,y,z}∩{x′ ,y′ ,z′ } ̸= /0. Now, consider an arbitrary triple of variables (x, y, z) on which M occurs as a sub-pattern. It follows that the instance which results after any instantiation of the three variables x,y,z contains no occurrence of M, since for each triple of variables (x′ ,y′ ,z′ ) on which M occurs in IC, at least one of its variables has been eliminated by instantiation.

Thus, after instantiation of at most three variables, IC does not contain M as a sub-pattern. This also holds for any version of IC obtained by instantiating the variables u,v. Since, as noted earlier, CSP SP (M) is tractable, we can therefore determine in polynomial time which instantiations of u, v can be extended to a solution of IC. We add a negative edge in I between points representing assignments p,q to variables u, v if p, q cannot be extended to a solution to IC, and then we delete all variables in C from I. Overall, we have proved that Ired can be constructed in polynomial time.

(A2): Suppose, for a contradiction, that we introduce the pattern P as a topological minor when reducing I to Ired. This occurrence of P must use the edge {u,v}. During the reduction from I to Ired, we can introduce negative (but not positive) edges between points p ∈ Au and q ∈ Av. Suppose that a negative edge {p,q} is introduced by the reduction from I to Ired. But this can only be the case if there was a path p = (u,w1, . . . ,wt , v) in the graph C with a sequence of negative edges in IC linking p to q via variables w1, . . . ,wk in IC: {p,s1}, {t1,s2}, {t2,s3} . . . {tk,q} with ∀i ∈ {1, . . . ,k}, si,ti ∈ Awi . This means that we can replace the edge {u,v} in the occurrence of P in Ired by a path (obtained from Ip for some path p in C by deleting unnecessary points and edges) so that P occurs as a topological minor in the original instance I. This contradiction shows that we cannot introduce P as a topological minor by reducing I to Ired.

Note that the number of instances of CSP SP (M) that need to be solved is O(nd 5 ).

7 Topological-minor tractable patterns extending acyclicity

In this Section we show how the well-known tractable class of acyclic instances can be generalised to obtain larger tractable classes defined by forbidding certain topological minors.

Theorem 7.1 Let P2 be any sub-pattern tractable pattern on three variables {x,y,z} where there is at most one negative edge between Ax and Ay, and between Ay and Az, and no edges between Ax and Az.

Let P be a pattern on variables {x, y, z,w} obtained by extending P2. The pattern P has six new points p1, p2 ∈ Ax, q1,q2 ∈ Aw, and r1, r2 ∈ Az, together with three new negative edges {p1, r1}, {p2, q1}, {q2, r2} (see Figure 4).

Any such P is a topological-minor tractable pattern.

Proof: The proof uses the generic scheme described in Section 5, so we only need to establish the two assumptions.

(A1) Suppose first that P2 occurs in IC as a sub-pattern on the path of variables x, y, z. As explained in Section 5, we assume that Ct is three connected. Then, by Menger's theorem there are three disjoint paths p1,p2,p3 from x to z in Ct . There must be two of these paths, say p1 and p2, which do not pass through y. But this implies that P occurs as a topological minor in I, since if either p1 or p2 passes by the edge {u, v} in the torso Ct , this edge can be replaced by pathR(u,v) which is a path from u to v in R, whose existence was shown in Section 5. Since this contradicts our initial assumption, we can assume that IC does not contain P2 as a sub-pattern. This also holds for any version of IC obtained by instantiating the variables u,v. Therefore we can determine in polynomial time which instantiations of u,v can be extended to a solution of IC. We add a negative edge in I between points representing assignments p,q to variables u,v if p,q cannot be extended to a solution to IC, and then we delete all variables in C from

✟

✠

I. Overall, we have proved that Ired can be constructed in polynomial time.

(A2) Suppose, for a contradiction, that we introduce the pattern P as a topological minor when reducing I to Ired. This occurrence of P must use the edge {u,v}. During the reduction from I to Ired, we can introduce negative (but not positive) edges between points p ∈ Au and q ∈ Av. Observe that, by definition, P contains at most one negative edge between any pair of variables. Suppose that a negative edge {p,q} is introduced by the reduction from I to Ired. But this can only be the case if there was a path p = (u,w1, . . . ,wt ,v) in the graph C with a sequence of negative edges in IC linking p to q via variables w1, . . . ,wk in IC: {p,s1}, {t1,s2}, {t2,s3} . . . {tk,q} with ∀i ∈ {1, . . . ,k}, si,ti ∈ Awi . Furthermore, in Ired, if there is a positive edge from p′ ∈ Au to q′ ∈ Av then there is necessarily a solution to IC including the assignments p′ and q′ (and hence a solution on the subinstance Ip of IC on the path p = (u,w1, . . . ,wt ,v) in C. This means that we can replace the edge {u, v} in the occurrence of P in Ired by a path (obtained from Ip for some path p in C by deleting unnecessary points and edges) so that P occurs in the original instance I. This contradiction shows that we cannot introduce P as a topological minor by reducing I to Ired.

Note that the number of instances of CSP SP (P2) that need to be solved is O(nd 2 ).

Theorem 7.1, tells us that 2-constraint patterns on three variables that are known to be sub-pattern-tractable [Cooper and Escamocher, 2012] can all be used as building blocks of topological-minor tractable patterns by adding two paths of negative edges. The resulting topological-minor tractable patterns are shown in Figure 4. For each of these patterns P, the pattern shown in Figure 2 is a sub-pattern and hence a topological minor of P. Thus, by the transitivity of occurrence as a topological minor, each tractable class CSP TM(P) necessarily contains all acyclic binary CSP instances.

Since detecting whether a fixed pattern occurs as a subpattern can be done in polynomial time [Cohen et al., 2012], and constructing a Tutte decomposition is also polynomialtime, these tractable classes can be identified in polynomial-

✟

✠

✟

✠

time. Similar remarks apply to the tractable classes identified in Proposition 6.4 and Proposition 6.1.

8 Detection of topological minors

For every fixed undirected graph H, there is an O(|V(G)|3 ) time algorithm that tests, given a graph G, if H is a topological minor of G [Grohe et al., 2011], so the detection of topological minors in graphs is fixed parameter tractable. However, for topological minor patterns in CSP instances the situation is different. We show in this section that it is NP-complete to determine whether the fixed 4-variable pattern PXX shown in Figure 5 occurs as a topological minor.

Theorem 8.1 The problem of deciding I ∈ CSP TM(PXX) is coNP-complete.

Proof: The problem is clearly in coNP, so it suffices to give a reduction from 3-SAT to the complement of the problem from the statement of the theorem. Let ISAT be an instance of 3-SAT with variables x1, . . . , xn and clauses C1, . . . ,Cm. We create a binary CSP instance I with variables {S,E}∪{pi | i = 0. . .n+m}∪{Xir,Xir | i = 1. . .n,r = 1. . .m}, such that determining I ̸∈ CSP TM(PXX) is equivalent to solving ISAT .

Consider the diagrams Pi,Tr,PS and PE shown in Figure 5. The variables in diagram Tr correspond to the literals in the clause Cr, with Xir corresponding to ¬xi occurring in clause r and Xir corresponding to xi occurring in clause r. That is, the example of diagram Tr in Figure 5 would correspond to the clause Cr = xj ∨¬xk ∨xℓ. It is implicitly meant that the index i goes from 1 to n, and the index r goes from 1 to m. The positive edges in I are the solid lines in these n+m+2 diagrams. Any pairs of points in I not shown to be connected with a positive edge by one of these diagrams is connected by a negative edge.

The only pairs of variables in I connected by more than one positive edge are {pn+m,E} and {p0,S}. So, if PXX occurs as a topological minor pattern in I, then the subproblems PE and PS must map injectively into PXX. Therefore, deciding whether PXX occurs as a minor pattern in I is equivalent to deciding whether there is a path p of positive edges from p0 to pn+m in I which passes through each variable at most once. We now show that this (graph) condition is equivalent to ISAT having a satisfying assignment.

If such a path p exists, then for each variable xi of ISAT , it must select in Pi either the upper path through variables Xir (r = 1, . . . ,m) or the lower path through variables Xir (r = 1, . . . ,m). Thus p selects a truth value for each variable xi: TRUE if p follows the upper of these two paths, FALSE otherwise. The positive edges in Pi (1 ≤ i ≤ n) use different points in AXir (shown as the bottom of the two points) from the positive edges in Tj (1 ≤ j ≤ m) (which use the top points); this ensures that p does indeed pass through the points p0, . . . , pn+m in this order.

The path p must pass from pn+r-1 to pn+r by one of the three paths: through variables X jr, Xkr or Xℓr, without passing through variables that have been already used by p. Thus, for p to exist it must have already assigned TRUE to one of the literals x j, ¬xk or xℓ of the clause Cr.

It follows that PXX occurs as a topological minor of I if and only if I has an appropriate path of positive edges, which occurs if and only if ISAT is satisfiable.

Theorem 8.1 shows that not all classes defined by forbidding topological minors can be identified in polynomial time. Certain uses of tractable classes require polynomial-time recognition, in particular, the automatic recognition and resolution of easy instances within general-purpose solvers. On the other hand, polynomial-time recognition of a tractable class C is not required for the construction of a polynomial-time solvable relaxation in C , nor in the proof (by a human being) that a subproblem of CSP encountered in practice falls in C .

9 Discussion

Not all patterns are topological-minor tractable. For example, for the two patterns, P, shown in Figure 6, CSP TM(P) is NPhard. This is implied by the following two facts which hold for both of these particular patterns, P:

1. CSP TM(P) =CSPSP(P).
2. CSP SP (P) is NP-complete [Cohen et al., 2012].

One long-term goal is to characterise precisely which patterns are topological-minor tractable.

We are also investigating other applications for topological minors, such as in variable elimination [Cohen et al., 2013].

The notion of a topological minor of a CSP instance, introduced here, allows a new approach to the definition of tractable classes of CSP instances. Although the examples of such classes obtained above may not prove to be especially significant in themselves, we believe that this new approach has great potential for systematically describing all tractable classes. However, to achieve further progress it may well be necessary to further refine or modify the definition of a topological minor given here. We regard this work as simply a first step towards a general topological theory of complexity for constraint satisfaction problems.