  We investigate the so-called recoverable robust assignment problem on
balanced bipartite graphs with $2n$ vertices, a mainstream problem in robust
optimization: For two given linear cost functions $c_1$ and $c_2$ on the edges
and a given integer $k$, the goal is to find two perfect matchings $M_1$ and
$M_2$ that minimize the objective value $c_1(M_1)+c_2(M_2)$, subject to the
constraint that $M_1$ and $M_2$ have at least $k$ edges in common.
  We derive a variety of results on this problem. First, we show that the
problem is W[1]-hard with respect to the parameter $k$, and also with respect
to the recoverability parameter $k'=n-k$. This hardness result holds even in
the highly restricted special case where both cost functions $c_1$ and $c_2$
only take the values $0$ and $1$. (On the other hand, containment of the
problem in XP is straightforward to see.) Next, as a positive result we
construct a polynomial time algorithm for the special case where one cost
function is Monge, whereas the other one is Anti-Monge. Finally, we study the
variant where matching $M_1$ is frozen, and where the optimization goal is to
compute the best corresponding matching $M_2$, the second stage recoverable
assignment problem. We show that this problem variant is contained in the
randomized parallel complexity class $\text{RNC}_2$, and that it is at least as
hard as the infamous problem \probl{Exact Matching in Red-Blue Bipartite
Graphs} whose computational complexity is a long-standing open problem
