A vertex deletion problem asks for at most k vertices whose removal makes a graph satisfy a property Pi. Such problems are typically NP-hard, and their polynomial-time approximation factors are in many cases tight under standard assumptions. Parameterized approximation relaxes the running time instead: given f(k) times a polynomial in n, can we do better than the polynomial-time factor allows? Two combinations recur: reduce the parameter and finish with an exact FPT algorithm, or solve most of the instance exactly and finish with a polynomial-time approximation.

When every minimal obstruction to Pi has size at most d, partial branching combined with the polynomial-time d-approximation already gives a parameterized approximation scheme. This is unavailable when obstructions are unbounded, as for Feedback Vertex Set, where they are cycles of arbitrary length. I will show how a sampling step can take the place of branching in this case, and how the running time improves further when the problem also admits a good polynomial-time approximation or a fast exact FPT algorithm.

The question changes character once vertices carry weights. For Weighted Vertex Cover no factor below 2 is known even in FPT time, and the total weight can be arbitrarily large and unrelated to k, so it cannot serve as a good parameter itself. Keeping k as the parameter and carrying the weight as a second budget W gives a problem in which no single factor is the right guarantee: the natural relaxation is bi-criteria, returning a set of size at most ak and weight at most bW. I will present a family of such algorithms for Vertex Cover trading the pair (a,b) against running time, how far this extends to d-Hitting Set, what is known when obstructions are unbounded, and the questions left open.