---
abstract: 'In this paper we give two characterisations of the class of reflexive graphs admitting [*distributive lattice polymorphisms*]{} and use these characterisations to address the problem of recognition: for a reflexive graph $G$ in which no two vertices have the same neighbourhood, we find a polynomial time algorithm to decide if $G$ admits a distributive lattice polymorphism.'
address: 'Kyungpook National University, Republic of Korea'
author:
- Mark Siggers
title: Distributive lattice polymorphism on reflexive graphs
---

[^1]

Introduction {#sect:results}
============

Motivation
----------

It is well known (see for example [@BJK]) that Constraint Satisfactions Problems, which provide a formulation for many combinatorial problems, can be stated as the problem of finding a homomorphism between structures. Moreover ([@FV98]) any such homomorphism problem can be reduced to the retraction problem for [*reflexive*]{} graphs- graphs in which every vertex has a loop.

The problem $\operatorname{Ret}(G)$ of retraction to $G$ is $NP$-complete for most reflexive graphs $G$ and in the case that the problem is known to be polynomial time solvable for some $G$, the polynomial time algorithm is tied to the existence of a [*polymorphism*]{} on $G$– an operation $f:V(G)^d \to V(G)$ that preserves edges– satisfying some nice identity.

A reflexive graph $G$ 