  We study the parameterized complexity of a broad class of problems called
"local graph partitioning problems" that includes the classical fixed
cardinality problems as max k-vertex cover, k-densest subgraph, etc. By
developing a technique "greediness-for-parameterization", we obtain fixed
parameter algorithms with respect to a pair of parameters k, the size of the
solution (but not its value) and \Delta, the maximum degree of the input graph.
In particular, greediness-for-parameterization improves asymptotic running
times for these problems upon random separation (that is a special case of
color coding) and is more intuitive and simple. Then, we show how these results
can be easily extended for getting standard-parameterization results (i.e.,
with parameter the value of the optimal solution) for a well known local graph
partitioning problem.
