  We survey the field of algorithms and complexity for graph problems
parameterized above or below guaranteed values, a research area which was
pioneered by Venkatesh Raman. Those problems seek, for a given graph $G$, a
solution whose value is at least $g(G)+k$ or at most $g(G)-k$, where $g(G)$ is
a guarantee on the value that any solution on $G$ takes. The goal is to design
algorithms which find such solution in time whose complexity in k is decoupled
from that in the guarantee, or to rule out the existence of such algorithms by
means of intractability results.
  We discuss a large number of algorithms and intractability results, and
complement them by several open problems.

Data Structures and Algorithms