The CSP-dichotomy of Bulatov [6] and Zhuk [17] tells us that the constraint satisfaction problem CSP(H) for a core relational structure H is in P if H admits a WNU-polymorphism, and is otherwise in NPC. It is difficult, however, to decide if H admits a WNU-polymorphism. So more tractable dichotomies, characterisations like the well known H-colouring dichotomy of [13] which says that the homomorphism problem Hom(H) for a simple graph H is in P if and only if H is bipartite, are still sought. One such dichotomy arose recently in relation to signed graphs [3, 4], and in this paper we work towards a generalisation of this. The definition of WNU-polymorphisms, as well as the definitions of many other now standard algebraic terms introduced in this section without definition, can be found in Section 2.

Henceforth, graphs are undirected graphs in which loops — edges of the form {v,v} — are allowed. If all vertices have loops, then the graph is reflexive, and if no vertices have loops, then it is irreflexive. We denote an edge {u,v} of a graph simply as uv, and write u v to mean that uv is an edge.

A signed graph is a graph G together with an assignment of a sign + or - to each edge. Introduced by Harary in [11] in 1955, there are numerous results about signed graphs. It will be convenient to view a signed graph G as a br-graph (for blue-red): a pair of graphs — GB, whose edges are called blue edges, and GR, whose edges are red edges — on the same vertex set. Signed graphs, as defined by Harary, were irreflexive and simple. But as is done in [3, 4] we allow loops, and allow GB∩GR to be non-empty. An edge in GB∩GR is technically two edges in G, one of each colour, but it is convenient to consider it a single edge with both colours. With this view in mind, such an edge is called bicoloured, and an edge is unicoloured if it is not bicoloured. If all edges of a br-graph G are unicoloured red edges, then G is called red, and if all edges are bicoloured, then G is called bicoloured. A br-graph G is irreflexive, or bipartite, or connected or such, if the underlying graph GB∪ GR is. We write u ∼ v to mean that uv is in GB∪ GR. Inherent to the concept of a signed graph is the operation of switching, introduced by Zaslavsky [16], in which, for a vertex v, one switches, with respect to GB and GR, the set of edges incident to v. As a loop at v can be considered to be switched twice, loops are unchanged by a switching. Bicoloured edges, being a red and a blue edge, are also unchanged by a switching. Two br-graphs are switching-equivalent if one can be changed to the other by a series of switchings. A unicoloured cycle is balanced if it has an even number of red edges, and so the term uni-balanced was introduced in [1] for a br-graph that is switching-equivalent to a graph in which all unicoloured cycles are balanced. It follows from a result of [16] that a br-graph is uni-balanced if and only if it is switching-equivalent to a br-graph in which all unicoloured edges are blue. As sign plays no role in this paper, any result we show for uni-balanced graphs also holds for graphs that are switching-equivalent to a br-graph in which all unicoloured edges are red.

As a homomorphism ϕ:G→H from a graph G to a graph H is a edge preserving vertex map, a homomorphism from a br-graph G to another br-graph H is a vertex map ϕ:G→H which preserves both red edges and blue edges. Defined in [15], a switch-homomorphism from G to H is a vertex map ϕ:G→H such that for some graph G' that is switching-equivalent to G, the map ϕ:G′→H is a homomorphism.

In [10], Foucaud and Naserasr introduced the decision problem S-Hom(H) for a given br-graph H: decide for a given br-graph G if there is a switch-homomorphism to H. They addressed the problem of classifying the complexity of S-Hom(H) in terms of H. A priori, S-Hom(H) is not a CSP problem, but in [3] the authors showed that it is polynomially equivalent to CSP(SH) for a br-graph SH called the switching graph of H, defined in Definition 2.3. From this, it follows by the CSP-dichotomy, that there is a complexity dichotomy. This dichotomy was characterised in [3] and [4].

The switch-core of a br-graph H is the unique minimal induced subgraph to which it admits a switch-homomorphism. A complexity dichotomy for the switch-homomorphism problem was conjectured in [3], and completed in [4].

Theorem 1.1 ([4]). For a br-graph H, the problem S-Hom(H) is in P if the switch-core of H has at most two edges, and is otherwise in NPC.

Our goal is to determine, for a given br-graph H, the complexity of the list version List-S-Hom(H) of the problem S-Hom(H).

Much has already been done in [1]. Building on known ideas that we explain in more detail in the next section, the authors first observe that List-S-Hom(H) is in P if and only if SH admits a semi-conservative WNU-polymorphism; this is defined at the end of Section 2. The goal then becomes to characterise the br-graphs H such that SH admits a semi-conservative WNU-polymorphism. The authors then go on to define a special bipartite-min ordering of the bipartite resolution BH of H, and define two obstructions to its existence, both of which are detectable in polynomial time: invertible pairs and chains in BH. The definition of BH is given at the beginning of Section 4.1. A restricted version of the definition of special bipartite-min ordering is given as Definitions 4.6 and 5.2. Restricted versions of the definitions of invertible pairs and chains is given as Definition 5.1.

Using these as their main tools, the authors of [1] characterise the br-trees admitting semi-conservative WNU-polymorphisms. The full characterisation is not easy to state, but for irreflexive trees, which can easily be shown to be uni-balanced, their characterisation agrees with the following conjecture.

Conjecture 1.2. For a uni-balanced br-graph H, the following are equivalent.

• (i) BH has no invertible pairs and no chains.

• (ii) BH has a special bipartite-min ordering.

• (iii) SH has a semi-conservative WNU-polymorphism.

The original main result of this paper was to prove Conjecture 1.2 for reflexive uni-balanced graphs. We are indebted to a reviewer who found fatal flaws in our proof of it. Our attempts to fix the flaws devolved into extensive casework, and so we abandoned it when a much more elegant proof came out in [2]. Though the approach in [2] was clearly the right approach, our approach was different than theirs and adds some valuable insight. Our proofs make significant use of symmetries in both the definition of SH and the definition of bipartite-min orderings, and using the results of [2], we get a strengthening of their result, explained below, for reflexive uni-balanced graphs.

Section 2 can be viewed as, perhaps, an expansion of this introductory section. We recall many required algebraic results of CSP theory and structural results about the list homomorphism problem for graphs.

In Section 3 we define a switch-symmetric polymorphism which commutes with the obvious symmetry in SH, and use it to observe that if a polymorphism of the red subgraph SHR of SH is switch-symmetric, then it is a polymorphism of SH. This is a useful tool in defining polymorphisms on SH, but also yields a quick result. It allows us to quickly prove Theorem 3.2 which characterises the br-graphs H such that SH admits a conservative WNU-polymorphism. This depends on known characterisations of graphs with conservative WNU-polymorphisms. As these do not exist for semi-conservative WNU-polymorphisms though, much work remains.

In Section 4 we make observations about a 'reduction to the bipartite case' for list homomorphisms of graphs that is given in [8], and show that parts of it extend transparently to br-graphs. In particular, this leads to the definition of a 'parity-symmetric' bipartite-min ordering, and the following strengthening of Conjecture 1.2.

Conjecture 1.3. For a uni-balanced br-graph H, the following are equivalent.

• (i) BH has no invertible pairs or chains.

• (ii*) BH has a parity-symmetric special bipartite-min ordering.

• (iii) SH has a semi-conservative WNU-polymorphism.

Conjecture 1.3 implies Conjecture 1.2, and indeed, it consists of Conjecture 1.2 and the following conjecture, the proof of which, for graphs, follows from non-trivial results in [8].

Conjecture 1.4. For a uni-balanced br-graph H, BH has a special bipartite-min ordering if and only if it has a parity-symmetric one.

Our main result is Theorem 5.5, which proves Conjecture 1.3 for reflexive uni-balanced graphs. This also proves Conjecture 1.4 for reflexive uni-balanced graphs. To be clear though, our result depends on the result of [2]. Our main contributions consist of Theorem 5.4, which gives the implication (ii*)⇒(iii) for bipartite uni-balanced graphs, and the technical Lemma 4.1, which allows us to reduce to the bipartite case: with the implication (i)⇒(ii) from [2], Lemma 4.1 allows us to show (i)⇒(ii*), and with Theorem 5.4, it gives us the the implication (ii*)⇒(iii) for all reflexive uni-balanced graphs. Lemma 4.1 is presented in some generality as it seems that it could be useful beyond the present paper.

The literature about the list homomorphism problem that we recall in Section 2 suggests many 'polymorphism collapses' that may be useful in finding a full characterisation of the complexity of List-S-Hom(H). While some have proved useful, some have been red herrings. In our final section, Section 6 we give examples showing that some of these collapses do not occur.

In this section we recall the definitions required to properly state our problem, and make some initial observations about it. Many of these observations can also be found in [1].

2.1. Structures, CSP, and List Homomorphism

A (relational) structure H consists of a set V=V(H) of vertices with a finite ordered set of finite arity relations Ri⊂Vk on V. The corresponding ordered set of the arities of the structure is called its type. A homomorphism between two structures of the same type is a vertex map that preserves each relation. The problem CSP(H) for a structure H is the problem of deciding if an instance structure G of the same type admits a homomorphism to H.

A graph H is viewed as a structure with one symmetric binary relation E, an edge uv corresponding to the pairs (u,v) and (v,u) in E. A vertex map V(G)→V(H) of graphs is a homomorphism between two graphs if and only if it is a homomorphism of the corresponding symmetric binary structures. So Hom(H) is polynomially equivalent to CSP(H).

In the list variation List-Hom(H) of the homomorphism problem Hom(H), an instance G comes attached with a list L(v)⊂V(H) for each vertex v∈V(G), and one must decide if there is a homomorphism ϕ:G→H such that ϕ(v)∈L(v) for each vertex v of G. This is equivalent to CSP(Hc) where Hc is the relational structure one gets from a structure H by adding a new unary relation LS={(s)∣s∈S} for each subset S⊂V(H).

The core C(H) of a structure H is the unique minimum induced substructure to which it admits a homomorphism. It is basic that CSP(C(H)) is polynomially equivalent to CSP(H).

A k-ary polymorphism ϕ of H is a homomorphism ϕ: Hk→ H (that is, a map preserving all relations of H), where Hk is the k-time categorical product of H with itself. It is idempotent if ϕ(h,h,…,h)=h for all h∈V(H), and it is conservative if ϕ(v1,…,vk)∈{v1,…,vk}. An idempotent polymorphism ϕ: Hk→ H, for k≥3 is weak near unanimity or WNU if for every choice of x,y∈V(H) we have

Theorem 2.1 (The CSP-dichotomy, [6, 17]) For a relational structure H the problem CSP(H) is in P if the core of H admits a WNU-polymorphism, and is otherwise in NPC.

In general it is difficult to find the core of a structure H, and tends to be difficult to give a non-algebraic description of the structures H for which CSP(H) is in P. For list colouring, it gets a little easier. For one, the structure Hc is always a core. It is easy to see that any polymorphism of Hc is conservative, so for list colouring problems we get the following corollary of Theorem 2.1 which Bulatov actually proved years earlier in [5].

Corollary 2.2. For a relational structure H the problem CSP(Hc) is in P if and only if the core of H admits a conservative WNU-polymorphism.

2.2. The switching graph

One might observe that S-Hom(H) for a br-graph H is not a CSP, so the above tools do not apply, but one of the main tools in [3] and [4] is the following construction which allows us to view S-Hom(H) as a CSP.

For a product A×B of sets or of graphs, we use πA to denote projection map onto A and πB the projection map onto B.

Definition 2.3. Let H be a br graph. For i∈S:={0,1} let H_i be the copy of H with vertex set {(v,i)∣v∈V(H)} for which πi((v,i))=v is an isomorphism. The switching graph SH of H is the br-graph on the set V(H)×S that we get from the disjoint union of H₀ and H₁ by adding the red edges (u,0)(v,1) and (u,1)(v,0) for every blue edge uv of H, and the blue edges (u,0)(v,1) and (u,1)(v,0) for every red edge uv of H.

See Figure 1 for an example of the switching graph construction. Blue edges are solid, while red edges are dashed.

Figure 1. A br-graph H and its switching graph 𝒮H.

Let the switch map fs:V(SH)→V(SH) be the automorphism of SH defined by fs((v,i))=(v,1−i). It is evident that the edge ufs(v) is red if uv is blue, and ufs(v) is blue if uv is red.

The following proposition implies that S-Hom(H) is polynomially equivalent to the homomorphism problem Hom(SH) for the br-graph SH.

Proposition 2.4 ([3]) For br-graphs G and H, G admits a switch-homomorphism to H if and only if it admits a homomorphism to SH.

2.3. Definition of List Switch-Homomorphism

Though the problems S-Hom(H) and Hom(SH) are polynomially equivalent, they have different list versions. For a br-graph H we define the following two problems.

List-S-Hom(H)

Instance: A br-graph G with lists L:V(G)→2V(H).

Question: Does G admit a switch-homomorphism ϕ:G→H preserving lists?

List-Hom(SH)

Instance: A br-graph G with lists L:V(G)→2V(SH).

Question: Does G admit a homomorphism ϕ:G→SH preserving lists?

The second problem is clearly equivalent to the CSP problem CSP(SHc). The first problem can also be made equivalent to a CSP using Proposition 2.4. Indeed, from the proof of this proposition, it is not hard to see that it is polynomially equivalent to CSP(SHsc) where we get SHsc from SHc by throwing away non-symmetric lists, i.e., throwing away the unary relation L_S for any subset S⊂V(H) that is not closed under action by the switch map s from Definition 2.3.

Clearly List-Hom(SH) encodes List-S-Hom(H) by taking only instances with symmetric lists, and as the full lists are symmetric, List-S-Hom(H) encodes Hom(SH) by taking instances with full lists on every vertex. Thus we have the following polynomial reductions.

Calling a polymorphism of SH semi-conservative if it conserves symmetric lists, Theorem 2.1 yields a nice algebraic description of the relationship between the problems List-S-Hom(H) and List-Hom(SH).

Fact 2.5. For a br-graph H, List-S-Hom(H) is in P if and only if SH admits a semi-conservative WNU-polymorphism, and List-Hom(SH) is in P if and only if SH admits a conservative WNU-polymorphism.

Proof. Everything would be immediate from Theorem 2.1 except that to apply it we need that the structures are cores, while the structure SHsc, which we use for List-S-Hom(H), need not be a core. So we show that if SH admits a semi-conservative WNU-polymorphism, then the core of SHsc admits a WNU-polymorphism. To get the core of SHsc we must identify the vertices (v,0) and (v,1) for any vertex v of H all of whose edges are bicoloured. Let r be the retraction of SH to its core that we get by making all of these identifications. It is easy to check that if ϕ:SHk→SH is a semi-conservative WNU-polymorphism, then ϕ′=r∘ϕ|r(SH)k is a WNU-polymorphism on the core r(SH).

2.4. Collapses of Conservative Polymorphisms

Our goal is a nice characterisation of the br-graphs H such that SH admits a (semi-)conservative WNU-polymorphism. In the case of other graph-like structures, such characterisations often come from the fact that a structure has a conservative WNU-polymorphism if and only if it has some other nicer polymorphism such as a conservative 3-NU-polymorphism (also known as a conservative majority polymorphism).

Definition 2.6. A polymorphism ϕ:H3→H on a graph H is 3-NU if for any x,y∈V(H), we have

It is clear that a 3-NU-polymorphism is WNU, but one can find many examples of structures with WNU-polymorphisms that do not have 3-NU-polymorphisms. owever, there is a collapse of these two types of polymorphisms for graphs.

Theorem 2.7 ([8]) A graph H has a conservative WNU-polymorphism if and only if it has a conservative 3-NU-polymorphism.

Another useful conservative WNU-polymorphism is disguised as an ordering. Recall that an ordering ≤ of a set V can be viewed as a 2-ary function min:V2→V such that min(u,v)=min(v,u)∈{u,v} for all u,v∈V.

Definition 2.8. An ordering ≤ of the vertices of a reflexive graph is a min ordering if the corresponding 2-ary function min is a polymorphism.

A graph with a min ordering admits the induced 3-ary operation min(a,b,c)=min(min(a,b),c) which is a conservative WNU-polymorphism of H; we call this the min polymorphism associated with the min ordering. For reflexive graphs, there is a collapse of WNU-polymorphisms to min orderings.

Definition 2.8. An ordering ≤ of the vertices of a reflexive graph is a min ordering if the corresponding 2-ary function min is a polymorphism.

A graph with a min ordering admits the induced 3-ary operation min(a,b,c)=min(min(a,b),c) which is a conservative WNU-polymorphism of H; we call this the min polymorphism associated with the min ordering. For reflexive graphs, there is a collapse of WNU-polymorphisms to min orderings.

Theorem 2.9 ([7]). For a reflexive graph H the following are equivalent.

• ᐧ The problem List-Hom(H) is in P.

• ᐧ H admits a conservative WNU-polymorphism.

• ᐧ H admits a min ordering.

• ᐧ H contains no invertible pairs.

The existence of min orderings is known to characterise the well known class of interval graphs, so a reflexive graph has a conservative WNU-polymorphism if and only if it is an interval graph. Min orderings are also known to be characterised by the fact that they satisfy the underbar property:

No non-empty irreflexive graph can have a min ordering, but there is a generalisation, called a bipartite-min ordering, defined in Section 4 on what we call the bipartite resolution BH of H, that exists for many irreflexive graphs.

It was shown in [9], for a graph H with a bipartite-min ordering, that the problem List-Hom(H) can be solved in polynomial time via the arc-consistency algorithm. In [12] the authors generalised the notion of bipartite-min orderings to digraphs, unifying many known list homomorphism characterisations.

Theorem 2.10. [12] For a graph H the following are equivalent.

• ᐧ The problem List-Hom(H) is in P.

• ᐧ H admits a conservative WNU-polymorphism.

• ᐧ H admits a bipartite-min ordering.

• ᐧ BH contains no invertible pairs.

Recall the switch automorphism fs: SH→ SH that maps (v,i) to (v,1-i). This is clearly also an automorphism of the red subgraph SHR of SH. A k-ary polymorphism ϕ of SH, or of SHR, is switch-symmetric if it commutes with fs:

Lemma 3.1. If a polymorphism of SHR is switch-symmetric, then it is a polymorphism of SH.

Proof. Let ϕ:(SHR)k→SHR be switch-symmetric. To see that it is a polymorphism of SH it is enough to observe that it is also a polymorphism of SHB. Let xi yi in SHB for each i∈[k]. By the definition of SH we have that xi  fs:(yi) in SHR for each i. So as ϕ is a polymorphism of SHR we get

is a red edge, and so ϕ(x1,…,xk) ϕ(y1,…,yk) is a blue edge. This is enough.

We will use this in Section 5, but for now we exhibit its utility by using it to characterise the graphs SH having conservative WNU-polymorphisms. This yields a simple complexity dichotomy for the problem List-Hom(SH).

Theorem 3.2. For a br-graph H, SH admits a conservative WNU-polymorphism if and only if SHR admits a conservative 3-NU-polymorphism.

The proof of this theorem takes the rest of the section, but consists mostly of observations about known results. We recall these results and then give the proof formally at the end of the section. First observe the following hierarchy of polymorphisms.

The first two implications are trivial; indeed, the first is by definition, and the second is because a polymorphism of a structure is a polymorphism of any relation of the structure. We get the third implication by applying Theorem 2.7 to the graph SHR.

To prove Theorem 3.2 it is enough to show that a 3-NU-polymorphism on SHR may be assumed to be switch-symmetric, as then by Lemma 3.1 we get that the four statements in (3) are equivalent. In fact one can assume more about the 3-NU-polymorphism on SHR.

Definition 3.3. A conservative 3-NU-polymorphism ϕ:H3→H is symmetric if it commutes with all automorphisms σ of H:

In [14], while giving a characterisation of the digraphs H for which List-Hom(H) is tractable, Hell and Rafiey found a useful omitted subgraph characterisation of digraphs with conservative NU-polymorphisms. Their definition is for digraphs, but we give it here for graphs.

Definition 3.4. A walk P=u0 u1 … un of a graph H avoids a walk Q=v0 v1 … vn of H of the same length if ui−1 vi for each i∈[n]. For a 3-tuple (a,b,c) of vertices of H, a b-excluder in H is a set of three walks B_a, B_b and B_c of the same length, starting at a,b and c respectively, such that B_a and B_c share the same last vertex, and B_b avoids B_a and B_c. See Figure 2. A 3-tuple (a,b,c) is a permutable triple if H contains an a-excluder, a b-excluder, and a c-excluder.

Figure 2. A b-excluder for (a, b, c)

In Theorem 4.1 of [14], it was shown that a graph H has a 3-NU-polymorphism if and only if it contains no permutable triples. In the proof, it was observed that if a graph H has no permutable triples, then for any 3-tuple (x1,x2,x3) in V(H)3, there is at least one i∈[3] such that there is no x_i-excluder in H for (x1,x2,x3). We isolate a fact shown within the proof of Theorem 4.1 of [14].

Lemma 3.5 ([14]) Let H be a graph with no permutable triples. Let ϕ(x1,x2,x3)=m if at least two of the entries are m, and otherwise let ϕ(x1,x2,x3)=xi where i is the minimum index such that there is no x_i-excluder in H for (x1,x2,x3). The function ϕ:H3→H is a conservative 3-NU-polymorphism of H.

It is clear that the existence of excluders for a triple is preserved under any automorphism s of H. The properties 'two of x₁, x₂ and x₃ being the same', and 'minimum index' are also preserved, so the conservative 3-NU-polymorphism defined in the lemma is symmetric. This allows us to prove Theorem 3.2.

Proof of Theorem 3.2. Let SHR have a conservative 3-NU-polymorphism ϕ. By the discussion following Lemma 3.5 we may assume that ϕ is symmetric, and so, as the switch map is an automorphism of SHR, switch-symmetric. By Lemma \ref{lem:ss}, ϕ is then a conservative 3-NU-polymorphism of SH, and so a conservative WNU-polymorphism. This completes the proof of the equivalence of the four polymorphisms in (3), and so proves Theorem 3.2.

In [8], Feder, Hell, and Huang, reduced the complexity of the list homomorphism problem for graphs to the bipartite (so irreflexive) case by showing that List-Hom(H) for any graph H is polynomially equivalent to List-Hom (BH) for a bipartite graph BH:=K2×H. Their result implies that H has a conservative WNU-polymorphism if and only if BH does. Their proof consists of two parts. Where 'parity-symmetric' polymorphisms on BH are defined below, the authors of [8] essentially prove the following two equivalences.

• (i) H has conservative WNU-polymorphism if and only if BH has a parity-symmetric conservative WNU-polymorphism.

• (ii) BH has a parity-symmetric conservative WNU-polymorphism if and only if it has a conservative WNU-polymorphism.

(To reconcile these statements with those of [8], the reader should observe that the graph H** of [8] is simply BH augmented with a relation that forces all polymorphisms to be parity-symmetric.)

The first statement is easy. In this section we observe that it generalises and extends to similar statements about polymorphisms of br-graphs, and in particular about polymorphisms of SH. The second statement is much harder and depends on structural results.

4.1. The bipartite resolution and the constant parity subgraph

Recall that for a graph H, the categorical product K2×H is the graph with vertex set {0,1}×V(H) in which (i,h) (i′,h′) if and only if i≠i′ and h h′.

Let B be the bicoloured K₂ on the vertex set {0,1}. For a br-graph H, the bipartite resolution of H is BH:=B×H. It is a bipartite br-graph with partite sets πB−1(0) and πB−1(1), so we call i=πB((i,v)) the parity of a vertex (i,v) and call the map

which is clearly an automorphism of BH, the parity flip map. A polymorphism ϕ of BH is parity-symmetric if it commutes with the parity flip map.

Let P be the set consisting of the following properties applying to polymorphisms of a graph H: k-NU, WNU, idempotent, conservative, and semi-conservative (if H is a switch graph).

For any subset P⊆P, a polymorphism ϕ of H is a P-polymorphism if it has all properties in P. The main result of this section is the following.

Lemma 4.1. For any br-graph H, and any subset P of P, H has a P-polymorphism ϕ if and only if BH has a parity-symmetric P-polymorphism Φ (called the bipartite resolution of ϕ).

Proof. This is immediate from Claims 4.2 and 4.3 given below.

For a vertex v=(v1,…,vk) in BHk, the parity pattern of v is the tuple

of its coordinates' parities. Over components of BH the parity pattern is constant up to component-wise action of the parity flip map fp. In particular the constant parity subgraph CPBHk of BHk, which is the subgraph induced on the vertices with parity patterns (0,0,…,0) or (1,1,…,1), is a union of components. A coordinate of a parity pattern is majority if at least half of the coordinates have the same parity. A homomorphism Φ: CPBHk→ BH is a P-homomorphism, for any P⊆P, if it satisfies those same conditions required of a polymorphism of BH to satisfy them, and is parity-symmetric if it commutes with fp.

Claim 4.2. For any br-graph H and any P⊆P, H has a k-ary P-polymorphism if and only if CPBHk has a parity-symmetric P-polymorphism.

Proof. The details of the proof are straightforward but tedious, and so we just outline the main points.

For a polymorphism ϕ:Hk→H, the map Φ: CPBHk→ BH defined for v=(v1,…,vk)∈V(CPBHk) by

is a parity-symmetric homomorphism, and for a parity-symmetric homomorphism Φ: CPBHk→ BH the map ϕ:Hk→H defined for v=(v1,…,vk) by

is a polymorphism; moreover, these constructions are inverse.

That ϕ is WNU or k−NU if and only if Φ is also straightforward. To verify that ϕ is idempotent, conservative, or semi-conservative if and only if Φ is, one need only observe that Φ preserves a list L⊂V(BH) if and only if ϕ preserves its intersections, πH(L∩πB−1(0)) and πH(L∩πB−1(1)), with each side of BH.

Claim 4.3. For any br-graph H and any P⊆P∪{parity-symmetric}, any P-homomorphism CPBHk→ BH extends to a P-polymorphism of BH.

Proof. Given a homomorphism Φ: CPBHk→ BH, extend it to a polymorphism of BH by defining it, on each component of CPBHk, to project onto some coordinate that is majority in the parity pattern of the component.

That this maintains the properties of idempotence, conservativity, and semi-conservativity is immediate from the observation that projections preserve all lists. That parity-symmetry is maintained is immediate from the fact that projections are parity-symmetric. That the properties k−NU and WNU are maintained uses the choice of projection, but it straightforward.

Applying Lemma 4.1 to the br-graph SH yields this useful observation.

Proposition 4.4. For br-graph H, SH has a semi-conservative WNU-polymorphism if and only if BSH has a parity-symmetric semi-conservative WNU-polymorphism.

We use this in conjunction with one more simple observation.

Fact 4.5. For any br-graph H, BSH and SBH are isomorphic.

Proof. They are both the graph with vertex set B×V(H)×S where (i,h,j) (i′,h′,j′) if and only if i≠i′ and h h′. The edge (i,h,j)(i′,h′,j′) is red if and only if hh' is red and j = j' or hh' is blue and j≠j′.

4.2. Bipartite-min orderings

As mentioned in the introduction, a graph cannot have a min ordering unless almost all of its vertices have loops. In [9], bipartite-min orderings were considered for bipartite graphs.

Definition 4.6. An ordering of the vertices of a bipartite graph H with partite sets U and V is a bipartite-min ordering if for any a,b∈U and a′,b′∈V, the underbar property (2) holds.

As a min-ordering ≤ of H is a 2-ary function min which defines a conservative 3-ary WNU-polymorphism min of H, (see before and after Definition 2.8) a bipartite-min ordering of H is two functions, one on the partite set U and one on V, that defines a conservative WNU-homomorphism from CP(BH3) to BH, so by Claim 4.3 extends to a conservative WNU-polymorphism of BH. So in the same way that a min-ordering of H yields a conservative WNU-polymorphism on H, a bipartite-min ordering of BH yields a conservative WNU-polymorphism on H. If this polymorphism of BH is parity-symmetric, it gives, by Lemma 4.1, a conservative WNU-polymorphism on H.

Viewing min orderings and bipartite-min orderings as functions, we get the following case of Lemma 4.1.

Fact 4.7. A graph H has a min ordering if and only if BH has a parity-symmetric bipartite-min polymorphism.

As useful as min orderings are, one looks to define them for br-graphs. This was done for trees and some other classes of br-graphs in [1]. The authors defined special min orderings of reflexive br-trees, and special bipartite-min orderings of irreflexive br-trees, and then showed that for br-graphs H with these orderings the problem List-S-Hom(H) can be solved in polynomial time.

Though explicit, the polynomial time algorithms from [1] and [2] are complicated. In this section we suggest an approach to these tractability proofs that is easier, depending on the CSP-dichotomy to sweep this complication under the rug.

We consider uni-balanced br-graphs. As mentioned in the introduction, it follows from a result of Zaslavsky in [16] that such graphs are switching-equivalent to a br-graph in which all unicoloured cycles are blue, so we will assume that our uni-balanced br-graphs have been switched to remove all unicoloured red edges. We thus talk only of blue edges, by which we mean unicoloured blue edges, and bicoloured edges. In the one place that we want to consider a bicoloured edge as blue, we say 'not necessarily unicoloured blue'. A neighbour of a vertex is called bicoloured or blue if it is adjacent via a bicoloured or blue edge.

The following definition is from [1] but is simplified here for uni-balanced graphs. Though we do not use the definition beyond observing that an invertible pair in a br-graph H corresponds with the known definition of an invertible pair in its underlying graph, we include the definition, as invertible pairs and chains appear so prominently in the statements of our results and conjectures.

Definition 5.1. Let H be a uni-balanced br-graph. Construct a digraph A on the vertex set V(H)2 by letting (b,t)→(b′,t′) if b~b′,t~t′, and b~t′. A pair (x,y) is an invertible pair if there are walks from (x,y) to (y,x), and from (y,x) to (x,y) in A. A good end is a pair (b,t) of vertices of H for which there is another vertex x that with a bicoloured edge to b and a blue edge to t. A bad end is a pair (b,t) for which there is another vertex y with a bicoloured edge to t and a blue edge to b. A chain in H is a directed walk in A from a good end to a bad end.

The following defintion is also a definition from [1] that has been simplified by restricting to uni-balanced graphs. Note that if H is uni-balanced, then so is BH.

Definition 5.2. Given a uni-balanced br-graph H, and a bipartite-min ordering of the underlying graph of BH, a vertex is special if all its bicoloured neighbours come before all its blue neighbours. The ordering is a special bipartite-min ordering if all vertices are special.

Our main theorem says that the existence of a special bipartite-min ordering on BH, for a reflexive uni-balanced graph H, yields a semi-conservative WNU-polymorphism on SH, so implies that List-S-Hom(H) is in P.

A blue component C of a uni-balanced graph H is a subgraph induced by a component of the subgraph of unicoloured blue edges. We note that a blue component may induce bicoloured edges, but is connected via blue edges.

Lemma 5.3. Let B be a bipartite uni-balanced br-graph having a special bipartite-min ordering, and let C be a blue component of B with maximum vertices u_a and u_b. Let xaxb be a blue edge in C, and let y_ay_b be an edge with xa≤ya≤ua and xb≤yb. Then y_ay_b is blue, and y_a and y_b are in C.

Proof. As C is a blue component there is a blue path from x_a to u_a, and somewhere it must cross yayb, so we may assume (by switching the roles of a and b if necessary) we have a blue path aba' in C with a≤ya<a′ and b≤yb. By the underbar property with the edge a'b we have ya b, and as b is special with a blue edge to a, y_ab is also blue. So y_a is in C. As yb>b we then get that yayb is blue by the speciality of y_a. So y_b is in C.

This shows that if there is a bicoloured edge yayb above a blue edge xaxb, then it must be above the whole blue component containing x_a and x_b.

We are now ready to prove the main result of the section.

Theorem 5.4. Let BH be a bipartite uni-balanced graph with a special bipartite-min ordering ≤. The switch graph S:=SBH has a semi-conservative WNU-polymorphism Φ. Moreover, if ≤ is parity-symmetric, then so is Φ.

Proof. For a vertex v of BH let bc(v) be the blue component containing v. By Claim 4.2 it is enough to define Φ:S3→ S on constant parity tuples. For such tuples we set

where A=min(a1,a2,a3) for the bipartite-min polymorphism min defined by ≤, and X is defined as follows. Calling (ai,xi) or simply a_i relevant if bc(ai)= bc(A), let

• ᐧ X=maj(x1,x2,x3) if all a_i are relevant; otherwise let

• ᐧ X=xi where i is the minimum i such that a_i is relevant.

The function Φ is clearly idempotent, and semi-conservative. To see that it is WNU, it is enough to show that A and X are both WNU. Certainly A is, to see that X is too, we assume that there is a repeated value in {(x1,a1),(x2,a2),(x3,a3)}, and so in {a1,a2,a3}. We show that the value of X is chosen from among {x1,x2,x3} depending on which of the a_i is repeated, and is unchanged under permuting the indices i = 1,2,3. Indeed, if the repeated a_i is not relevant, then X is the other x_i. If the repeated a_i is relevant, while the other is not, X is the repeated x_i. If all are relevant, then X is majority, and so is the repeated x_i. In all cases, X is WNU. Observe also that Φ is switch-symmetric, as complementing the x_i does not effect A, and so does not effect which x_i is returned by X.

What remains to be shown, for the first statement of the theorem, is that Φ is a homomorphism. As it is switch-symmetric, by Lemma 3.1 it is enough to show that it preserves (not necessarily unicoloured) blue edges. Assume that (ai,xi) (bi,yi) is a blue or bicoloured edge for i=1,2,3. We show that

is a blue or bicoloured edge.

Indeed, as min is a polymorphism of the underlying graph BHB= BHB∪ BHR of BH, we have

in BHB, so AB is a blue or bicoloured edge of BH. If it is bicoloured, then whatever X and Y are, we have that (A,X)(B,Y) is a bicoloured edge, and we are done. We must show that if AB is blue, then X = Y.

Assume that AB is blue. First we claim, for all i, that if a_i is relevant, then a_ib_i is blue, making xi=yi, and implying that b_i is relevant. Indeed, if a_i is relevant, we have A≤ai and a_i is in bc(A). As AB is blue we have bc(B)=bc(A), and so any bicoloured neighbour of a_i must be below B by Lemma 5.3. Thus a_ib_i is a blue edge, as claimed, making b_i relevant. Similarly a_i is relevant if b_i is, and this holds for all relevant arguments, so with the fact that xi=yi for these arguments, we get X = Y.

For the second statement of the theorem, we have that A is parity-symmetric by definition, as ≤ is parity-symmetric, so it is enough to observe that X is unchanged by replacing the a_i with ps(ai). As A is parity-symmetric, doing so does not change which a_i are relevant, so this is immediate from the definition of X.

We finish off this section by showing that our theorem implies Conjecture 1.3 for reflexive uni-balanced graphs.

Theorem 5.5. For a reflexive uni-balanced br-graph H, the following are equivalent.

• (i) H has no invertible pairs or chains.

• (ii*) BH has a parity-symmetric special bipartite-min ordering.

• (iii) SH has a semi-conservative WNU-polymorphism.

Proof. In Theorem 4 of [2] it is shown that if H has no invertible pairs or chains, then H has a special min ordering. By Fact 4.7, a min ordering of H is exactly a parity-symmetric bipartite-min ordering of BH, and by definition, the first is special if and only if the second is, so we have the implication (i)⇒(ii*).

If BH has a parity-symmetric special bipartite-min ordering, Theorem 5.4 gives a parity-symmetric semi-conservative WNU-polymorphism of SBH. This is BSH by Fact 4.5, and so by Proposition 4.4, SH has a semi-conservative WNU-polymorphism. This gives us (ii*)⇒(iii).

Implication (iii)⇒(i) also uses known results. Assume that SH has a semi-conservative WNU-polymorphism. Then the problem List-S-Hom(H) is in P by Fact 2.5, and in particular it is in P when restricting to blue instances. As the underlying graph of H is exactly the blue subgraph HB, switching does not help for blue instances, and so List-S-Hom(H) for blue instances is just List-Hom(HB). Thus List-Hom(HB) is in P, and so HB has no invertible pairs by Theorem 2.10. By definition, an invertible pair of H is an invertible pair of the underlying graph, which in this case is HB, and so H has no invertible pairs. In [1] it is shown that chains in H omit semi-conservative WNU-polymorphisms on SH, so it has no chains either.

The following questions arise naturally when considering the complexity dichotomy for List-S-Hom(H), and when observing the various polymorphism collapses we have mentioned in the paper.

Question 6.1. Is it true for a br-graph H that

• (i) SH has a semi-conservative WNU if and only if it has a parity-symmetric one?

• (ii) SH has a semi-conservative WNU-polymorphism if and only if it has a conservative WNU-polymorphism?

• (iii) SH has a semi-conservative WNU-polymorphism if and only if it has a semi-conservative 3-NU-polymorphism?

Part (i) is certainly tempting. Using the results and ideas of Section 4 it is the key to getting a full reduction to the bipartite case: List-S-Hom(H)=polyList-S-Hom(BH). Part (ii) was tempting, as it would have reduced the whole proof of Theorem 3.2, including the part from [1], to Section 3. Part (iii) was also tempting, as it would have reduced the proof to Sections 3 and 4. We now have countless counter-examples giving negative answers to these last two questions. We give one in the proposition below.

Proposition 6.2. Where T is the br-graph on the left of Figure 3, PT has a semi-conservative WNU-polymorphism but no conservative WNU-polymorphism or semi-conservative 3-NU-polymorphism.

Figure 3. The tree T, the switch-core of 𝒫T, and its red subgraph R

Proof. That PT has a semi-conservative WNU-polymorphism is shown in [1], and also follows from Theorem 5.4. Indeed, ordering the vertices of T according to their position in the figure as one moves up the page; except putting the top vertex in the bicoloured path below its neighbour, we have a special bipartite-min ordering of T.

It is not too hard to verify that the triple (a2,b1,c1) in R is a permutable triple, showing that it and so PTR (of which it is an induced subgraph) can have no conservative WNU-polymorphism.

We show now that R can have no semi-conservative 3-NU-polymorphisms. Note that symmetric lists are now those for which if b_i is in a list, then c_i is also, and vice-versa.

Assume, towards contradiction, that ϕ is a semi-conservative 3-NU-polymorphism of R. There is no valid image for ϕ(a2,b1,c1). Indeed, if ϕ(a2,b1,c1)=a2, then ϕ(a1,b0,c0)=a1, and ϕ(a2,d,d)=a2. This contradicts the fact that ϕ is 3-NU. So without loss of generality we may assume that ϕ(a2,b1,c1)=b1. But then we see that ϕ(a1,b2,c2)=b2, so ϕ(a0,b1,c1)=b1, so ϕ(c0,b2,c2)∈{b0,b2} and so ϕ(c1,b1,c1)=b1. This again contradicts the fact that ϕ is 3-NU.

In [1] the authors observe that there are infinitely many trees having semi-conservative WNU-operations that contain T as an induced subgraph. The proof works for all of these.

We thank the authors of [1] for early copies of their manuscript, and Pavol Hell in particular for generously directing us towards key ideas on several occasions. We thank an anonymous reviewer for a very detailed reading which revealed essential mistakes in an earlier version of the paper.