|
|||
|
IMADA - Department of Mathematics and Computer Science |
|
Parameterized complexity has now established itself as one of the standard methodologies to cope with computationally hard problems. Kernelization reductions are a means of characterizing "parameterized tractable" problems and hence provide a core method to arrive at efficient parameterized algorithms. From a practical viewpoint, they neatly correspond to the heuristic idea of a clever preprocessing. In a certain sense, the smaller the kernel we can obtain, the better the algorithm. We will explain this idea with the example of the Dominating Set Problem. Moreover, small (linear) kernels yield algorithms where the seemingly unavoidable combinatorial explosion can be limited in a way that the algorithms behave like $O(c^{\sqrt{k}n})$, where $k$ is the parameter of the problem, e.g., a bound on the size of the dominating set. Then, we will exhibit recent results showing that (under the standard complexity assumption P not equal to NP) not always very small kernels can be expected for parameterized tractable problems. Host: Kim Skak Larsen
SDU HOME | IMADA HOME | Previous Page Last modified: February 6, 2004. Joan Boyar (joan@imada.sdu.dk) |