Semi-lattice polymorphisms

Pavol is visiting from Vancouver, and we are talking about a problem with a paper. We would like a polynomial algorithm to decide if a graph has a semilattice polymorphism. I say that I think a Lexicographic breadth first search might do the trick. He says, "It doesn't seem to me like that would do it." I suggest we take a break.

We go outside to walk around campus for a bit. He enjoys the sun- it refreshes him, counters his jet-lag. We walk towards North Gate. There are a lot of coffee shops at the North Gate- Korea is a proliferation of coffee shops- but we aren't going there. We are just walking to walk. Or so Pavol thinks.

We are walking on a path of flattened stones. When I walk with Lucy on such a path, we sing out "Jing, Kom, Tali" in syncopation with our steps. Jing kom tali is the Korean phrase for a bridge of individual stones lined across a stream or river. We aren't crossing a river, but if we step off the stones, an alligator will eat us, so our chant is somehow appropriate. Pavol knows nothing of the alligators, and doesn't sing "Jing, Kom, Tali", but luckily, he doesn't step off the stones either.

As we are walking, I point to a stone ahead, "You see that stone?"

"Yes."

I walk up onto the stone, and start rocking back and forth. He watches. I look at him with an expression that says "Well?"

He mirrors the expression.

"You didn't know it would do that, did you?" I ask.

"No."

"It just goes to show, that not everything is how it seems."

"No." he says, agreeing.

"Then let's go back and try that Lexicographic breadth first search." I say.

Turns out, it didn't work. The moral of this story: probably it's NP-complete to decide if a reflexive graph has a semilattice polymorphism.