Tilbake til søkeresultatene

FRINATEK-Fri prosj.st. mat.,naturv.,tek

Parameterized Algorithms

Tildelt: kr 7,3 mill.

The question if P=NP is today maybe the most famous mathematical problem. It has strong ties to practical computing and the central question facing the proposed research project in 'Parameterized Algorithms' is: how to cope with the NP-complete problems? Giving a better answer to this question will have important impact on both the mathematical and practical settings. The introduction of a second dimension to complexity analysis results in a new and refined notion of efficiency in the form of the complexi ty class FPT (Fixed Parameter Tractability). FPT is reasonable and robust just as P is and it is probably better for coping with NP-complete problems. In this way parameterized complexity constitutes a 'slicewise' attack on the NP-complete problems, under the motto 'tractability by the slice'. A recent argument in favor of FPT is in the form of 'Polynomial-Time Preprocessing' which we intend to develop further. This view of FPT leads to the important new research topic of 'Kernelization Bounds'. We will also focus on further developments in 'Parameterized Algorithm Design Techniques' and in the important, but partially overlooked, issue of 'Choice of Parameter'. The principal aims of the proposed research can be outlined as follows: 1.Establish improved upper and lower kernelization bounds for important combinatorial problems, and develop an appropriate notion of kernel-preserving reductions. 2.Refine the taxonomy of parameterized algorithm design techniques, both by combination of known techniques and by development of new ones, in particular for P-time kernelization. 3.Develop a complexity-ordering of parameters, for example by investigating for pairs of graph parameters A and B the parameterized complexity of computing value of A on graphs having fix ed value of B.

Budsjettformål:

FRINATEK-Fri prosj.st. mat.,naturv.,tek