  Lubiw showed that several variants of Graph Isomorphism are NP-complete,
where the solutions are required to satisfy certain additional constraints
[SICOMP 10, 1981]. One of these, called Isomorphism With Restrictions, is to
decide for two given graphs $X_1=(V,E_1)$ and $X_2=(V,E_2)$ and a subset
$R\subseteq V\times V$ of forbidden pairs whether there is an isomorphism $\pi$
from $X_1$ to $X_2$ such that $\pi(i)\neq j$ for all $(i,j)\in R$. We prove
that this problem and several of its generalizations are in fact in FPT:
  - The problem of deciding whether there is an isomorphism between two graphs
that moves k vertices and satisfies Lubiw-style constraints is in FPT, with k
and the size of $R$ as parameters. The problem remains in FPT if a CNF of such
constraints is allowed. It follows that the problem to decide whether there is
an isomorphism that moves exactly k vertices is in FPT. This solves a question
left open in our article on exact weight automorphisms [STACS 2017].
  - When the weight and complexity are unrestricted, finding isomorphisms that
satisfy a CNF of Lubiw-style constraints can be solved in FPT with access to a
GI oracle.
  - Checking if there is an isomorphism $\pi$ between two graphs with
complexity t is also in FPT with t as parameter, where the complexity of a
permutation is the Cayley measure defined as the minimum number t such that
$\pi$ can be expressed as a product of t transpositions.
  - We consider a more general problem in which the vertex set of a graph X is
partitioned into Red and Blue, and we are interested in an automorphism that
stabilizes Red and Blue and moves exactly k vertices in Blue, where k is the
parameter. This problem was introduced by [Downey and Fellows 1999], and we
showed [STACS 2017] that it is W[1]-hard even with color classes of size 4
inside Red. Now, for color classes of size at most 3 inside Red, we show the
problem is in FPT.
