  A backdoor in a finite-domain CSP instance is a set of variables where each
possible instantiation moves the instance into a polynomial-time solvable
class. Backdoors have found many applications in artificial intelligence and
elsewhere, and the algorithmic problem of finding such backdoors has
consequently been intensively studied. Sioutis and Janhunen (Proc. 42nd German
Conference on AI (KI-2019)) have proposed a generalised backdoor concept
suitable for infinite-domain CSP instances over binary constraints. We
generalise their concept into a large class of CSPs that allow for higher-arity
constraints. We show that this kind of infinite-domain backdoors have many of
the positive computational properties that finite-domain backdoors have: the
associated computational problems are fixed-parameter tractable whenever the
underlying constraint language is finite. On the other hand, we show that
infinite languages make the problems considerably harder: the general backdoor
detection problem is W[2]-hard and fixed-parameter tractability is ruled out
under standard complexity-theoretic assumptions. We demonstrate that backdoors
may have suboptimal behaviour on binary constraints -- this is detrimental from
an AI perspective where binary constraints are predominant in, for instance,
spatiotemporal applications. In response to this, we introduce sidedoors as an
alternative to backdoors. The fundamental computational problems for sidedoors
remain fixed-parameter tractable for finite constraint language (possibly also
containing non-binary relations). Moreover, the sidedoor approach has appealing
computational properties that sometimes leads to faster algorithms than the
backdoor approach.
