Nonstandard dual parametrization of graph problems One fundamental result in parameterized complexity of graph problems is that VERTEX COVER parameterized by the solution size $k$ is fixed-parameter-tractable (FPT). On the other hand, when parameterized by the "dual parameter" $|V(G)|-k$, it becomes equivalent to INDEPENDENT SET parameterized by solution size (because any vertex cover is the complement of an independent set), and thus it is W[1]-hard.

Although this seems less natural, I am interested in the parameterized complexity of VERTEX COVER for the parameter $|E(G)|-k$. This is a larger parameter than $|V(G)|-k$. Is VERTEX COVER FPT for this parameter?

Note: I am also interested in similar parameterizations for other graph problems (e.g. DOMINATING SET). The only place where I have seen both kinds of dual parameters studied is for the hypergraph problem TEST COVER in the 2012 paper "Parameterized Study of the Test Cover Problem" by Crowston, Gutin, Jones, Saurabh and Yeo. (also on arXiv)

Edit (04/12/2016): This parameterization is also studied for the other hypergraph problem HITTING SET in the 2011 paper Kernels for below-upper-bound parameterizations of the hitting set and
directed dominating set problems by Gutin, Mones and Yeo (arXiv link).
I think this problem is FPT. Suppose that the graph contains a path on $2k+1$ vertices. Then, I claim the answer is YES: we select the second, fourth, sixth, etc. vertices of this path in a solution and remove them from the graph. We now have a graph $G'$ with $|E(G')|\le |E(G)|-2k$. It is easy to find a vertex cover of $G'$ with size at most $|E(G')|$. Together with the removed vertices this gives a vertex cover of size at most $|E(G)|-k$ for $G$.

If the graph does not contain a path on $2k+1$ vertices, then a DFS tree of the graph has height at most $2k+1$, and hence can be used to construct a tree decomposition of width at most $2k$. We can then solve Vertex Cover optimally with the standard algorithm for treewidth.