  Vertex Cover parameterized by the solution size k is the quintessential
fixed-parameter tractable problem. FPT algorithms are most interesting when the
parameter is small. Several lower bounds on k are well-known, such as the
maximum size of a matching. This has led to a line of research on
parameterizations of Vertex Cover by the difference of the solution size k and
a lower bound. The most prominent cases for such lower bounds for which the
problem is FPT are the matching number or the optimal fractional LP solution.
We investigate parameterizations by the difference between k and other graph
parameters including the feedback vertex number, the degeneracy, cluster
deletion number, and treewidth with the goal of finding the border of
fixed-parameter tractability for said difference parameterizations. We also
consider similar parameterizations of the Feedback Vertex Set problem.
