| Before starting a slow and complex exact algorithm on a computationally hard problem, one often first applies a data reduction or preprocessing algorithm. With a relatively fast algorithm, the input is transformed to an equivalent input which is hoped to be (significantly)smaller of size compared to the original input. In this project, a fundamental study is being made of such data reduction algorithms, in particular we look at the trade-off between the running time of a data reduction algorithm, and the size of a reduced instance. An important tool for this study is the notion of kernelization from fixed parameter tractability theory. We aim at extending this theory with new methods to obtain positive and negative results, and apply these to concrete problems of theoretical and practical interest. |
