  The CONTRACTION(vc) problem takes as input a graph $G$ on $n$ vertices and
two integers $k$ and $d$, and asks whether one can contract at most $k$ edges
to reduce the size of a minimum vertex cover of $G$ by at least $d$. Recently,
Lima et al. [JCSS 2021] proved, among other results, that unlike most of the
so-called blocker problems, CONTRACTION(vc) admits an XP algorithm running in
time $f(d) \cdot n^{O(d)}$. They left open the question of whether this problem
is FPT under this parameterization. In this article, we continue this line of
research and prove the following results:
  1. CONTRACTION(vc) is W[1]-hard parameterized by $k + d$. Moreover, unless
the ETH fails, the problem does not admit an algorithm running in time $f(k +
d) \cdot n^{o(k + d)}$ for any function $f$. In particular, this answers the
open question stated in Lima et al. [JCSS 2021] in the negative.
  2. It is NP-hard to decide whether an instance $(G, k, d)$ of CONTRACTION(vc)
is a yes-instance even when $k = d$, hence enhancing our understanding of the
classical complexity of the problem.
  3. CONTRACTION(vc) can be solved in time $2^{O(d)} \cdot n^{k - d + O(1)}$.
This XP algorithm improves the one of Lima et al. [JCSS 2021], which uses
Courcelle's theorem as a subroutine and hence, the $f(d)$-factor in the running
time is non-explicit and probably very large. On the other hard, it shows that
when $k=d$, the problem is FPT parameterized by $d$ (or by $k$).
