RELATIONAL STRUCTURES ADMITTING CERTAIN 6-ARY TAYLOR POLYMORPHISMS ARE NP-COMPLETE TARGETS
MARK H. SIGGERS
Abstract. Here we give the combinatorial argument that is at the heart of my paper “A Strong Mal’cev Condition for Locally Finite Varieties omitting Type 1”.
1. Introduction
In [6], I showed that the problem of deciding if a core relational structureH is one of those that is conjectured in [1] to yield a polynomial time solvable problem CSP(H), is itself an NP problem. As the result had more interesting consequences in Universal Algebra, I wrote the proof from that point of view. Here I give my original proof, which is purely combinatorial. The proof is an example of the fibre construction developed in [5], [3], and [4]. We prove the following.
Theorem 1.1. If a core relational structure has no idempotent polymorphisms φ such that the following identity holds for all pairs (x, y) of vertices in V(H), then CSP(H)is NP-complete.
φ(x, x, x, x, y, y) =φ(x, y, x, y, x, x) andφ(y, y, x, x, x, x) =φ(x, x, y, x, y, x). (1) A polymorphism φof H is idempotent ifφ(v, v, . . . , v) = v for all vertices v in H. This and all other basic CSP definitions can be found on [4].
We use only the fact, which follows from the H-colouring Dichotomy of Hell and Neˇsetˇril [2] ( a paper which apparently I must cite in everything I write) that CSP(T) is NP-complete for any simple graphT containing a triangle.
Proof. LetH be a core relational structure having no idempotent 6-ary polymor- phism satisfying identities (1). It is well known, see [4], that a core H is NP- complete if and only if its idempotent reduct is, thus we will assume that the only polymorphisms ofHare idempotent.
We give a polynomial time construction that provides, for any instance G of CSP(T), an instanceG∗of CSP(H) such that
G→T ⇐⇒ G∗→H.
This encodes CSP(T), which is NP-complete, in CSP(H), so CSP(H) is also NP- complete.
It the proof we will use several copies of some ordered vertex setW∗, and we will consider a function defined on one of these copies, to be defined on another copy.
So if I have copies W1= (v11, . . . vw1) andW2 = (v21, . . . , vw2) ofW∗= (v1, . . . , vw), and define the functionf onW1, then say some other function φis equal tof on W2, then I meanφ(v2i) =f(vi1) for alli. If we say we identify two such copies, say W1 andW2 vertexwise, we mean we identifyvi1andv2i for alli.
1
2 MARK H. SIGGERS
W1= (v1, v1, v1, v1, v2, v2), (v2, v2, v1, v1, v1, v1), (v2, v2, v2, v2, v1, v1), (v1, v1, v2, v2, v2, v2), (v1, v1, v1, v1, v3, v3), (v3, v3, v1, v1, v1, v1), (v3, v3, v3, v3, v1, v1), (v1, v1, v3, v3, v3, v3),
. . .
(vn−1, vn−1, vn−1, vn−1, vn, vn), (vn, vn, vn−1, vn−1, vn−1, vn−1) (vn, vn, vn, vn, vn−1, vn−1), (vn−1, vn−1, vn, vn, vn, vn)
W2= (v1, v2, v1, v2, v1, v1), (v1, v1, v2, v1, v2, v1), (v2, v1, v2, v1, v2, v2), (v2, v2, v1, v2, v1, v2), (v1, v3, v1, v3, v1, v1), (v1, v1, v3, v1, v3, v1), (v3, v1, v3, v1, v3, v3), (v3, v3, v1, v3, v1, v3),
. . .
(vn−1, vn, vn−1, vn, vn−1, vn−1), (vn−1, vn−1, vn, vn−1, vn, vn−1) (vn, vn−1, vn, vn−1, vn, vn), (vn, vn, vn−1, vn, vn−1, vn)
.
Figure 1. Subsets W1 and W2 of M =H6: In each of W1 and W2, the same four 6-tuples are repeated for each pair of vertices ofH.
First we build an edge-replacement gadgetM.
The Gadget M.LetV(H) ={v1, . . . , vn}. LetM =H6and letW1andW2⊂V(M) be the ordered sets of 4· n2
6-tuples each shown in Figure 1.
The GraphT. LetW∗ be an ordered set of 4· n2
vertices. We consider bothW1 andW2as copies ofW∗, with vertices in the orders shown in the figure. , and any function LetT be the digraph with vertex set
V(T) ={ψ|W1 |ψ:H6→H is a homomorphism}
and arc set defined f → g if there is a homomorphism ψ : H6 → H such that ψ|W1 =f andψ|W2 =g.
6-ARY TAYLOR POLYMORPHISMS 3
Since σ : (x1, x2, x3, x4, x5, x6) → (x3, x5, x1, x6, x2, x4) is an automorphism of M =H6that mapsW1toW2andW2toW1,E(T) is well defined and symmetric.
Observe also thatT is irreflexive (loopless). Indeed any homomorphismφ:M → H is an idempotent 6-ary polymorphism of H, so the assumption of the theorem gives us that there is some choice ofx=vi and y =vj that does not satisfy the identities (1). Thusψ|W1 andψ|W2 are different functions, soT has no loops.
Finally, observe thatT contains a triangle. Indeed, the projections of M =H6 restrict onW1and onW2to only three different functions (vertices ofT) and that each of the six projections puts a different arc inE(T) between these functions.
The Fibre Construction G 7→ G∗. Given a graph G, arbitrarily orient its edges, and let beG∗ defined as follows.
(i) For each vertexv ofGletWv be a copy of the setW∗.
(ii) For each edgeuvofGletMuv be a copy ofM, and identify the copies of W1andW2inMuvbe identified vertexwise withWuandWvrespectively.
Putting this all together. Now we show thatG→T ⇐⇒ G∗→H. First, assume thatφ:G∗ →His a homomorphism. Then one can check that
v7→φ|Wv ∈V(T) is a homomorphism ofG→T.
On the other hand, assume that φ : G → T is a homomorphism. Define φ0 : G∗ → H as follows. For each v ∈ V(G) let φ0 be equal to φ(g) on Wg, (recall that vertices of T are functions on W∗). For each edge uv of G, φ(u)φ(v) is an edge of T, so there exists a homomorphism ψ : H6 → H such thatψ|Wu =φ(u) and ψ|Wv = φ(v). So we can extend φ0 to ψ on Muv. Thus we extend φ0 to a homomorphismφ0 :G∗→H.
References
[1] A. Bulatov, P. Jeavons, A. Krokhin, Classifying the complexity of constraints using finite algebras.SIAM J. Comput. 34 (2005), no. 3, 720–742.
[2] P. Hell, J. Neˇsetˇril,On the complexity ofH-colouringJ. Combin. Theory B 48 (1990) 92-100.
[3] J. Neˇsetˇril, M. SiggersA New Combinatorial Approach to the CSP Dichotomy Classification.
Submitted (2007).
[4] J. Neˇsetˇril, M. Siggers, L. ZadoriThe CSP Dichotmony Classification and the Fibre Con- structionSubmitted (2008).
[5] M. Siggers,Dichotomy for Bounded DegreeH-colouring.Submitted, (2007)
[6] M. Siggers,A Strong Mal’cev Condition for Locally Finite Varieties Omitting Type 1Man- uscript.
