Parameterized approximation via fidelity preserving transformations

We motivate and describe a new parameterized approximation paradigm which studies the interaction between approximation ratio and running time for any parametrization of a given optimization problem. As a key tool, we introduce the concept of an -, for . Applying such transformation to a parameterized problem instance decreases the parameter value, while preserving the approximation ratio of (or ). Moving even beyond the approximation ratio, we call for a new type of . Our -shrinking transformations can be used to obtain kernels which are smaller than the best known for a given problem. The smaller “-fidelity” kernels allow us to obtain an exact solution for the more efficiently, while obtaining an approximate solution for the original instance. We show that such fidelity preserving transformations exist for several fundamental problems, including , , and .