Kernelization --- preprocessing with a guarantee

摘要: Data reduction techniques are widely applied to deal with computationally hard problems in real world applications. It has been a long-standing challenge formally express the efficiency and accuracy of these "pre-processing" procedures. The framework parameterized complexity turns out be particularly suitable for mathematical analysis pre-processing heuristics. A kernelization algorithm is which simplifies instances given as input polynomial time, extent simplification desired quantified help additional parameter. We give an overview some early work area also survey newer that have emerged design algorithms. We outline Bodlaender et al. [9] Fortnow Santhanam [38] showing lower bounds under reasonable assumptions from classical theory, highlight recent results strengthen generalize this framework.