  The constraint satisfaction problem (CSP) on a finite relational structure B
is to decide, given a set of constraints on variables where the relations come
from B, whether or not there is a assignment to the variables satisfying all of
the constraints; the surjective CSP is the variant where one decides the
existence of a surjective satisfying assignment onto the universe of B.
  We present an algebraic framework for proving hardness results on surjective
CSPs; essentially, this framework computes global gadgetry that permits one to
present a reduction from a classical CSP to a surjective CSP. We show how to
derive a number of hardness results for surjective CSP in this framework,
including the hardness of the disconnected cut problem, of the no-rainbow
3-coloring problem, and of the surjective CSP on all 2-element structures known
to be intractable (in this setting). Our framework thus allows us to unify
these hardness results, and reveal common structure among them; we believe that
our hardness proof for the disconnected cut problem is more succinct than the
original. In our view, the framework also makes very transparent a way in which
classical CSPs can be reduced to surjective CSPs.

Computational Complexity