Tilbake til søkeresultatene

IS-DAAD-Forskerutveksl. Norge-Tyskland

Obtaining efficient algorithms by input restrictions: re-drawing the borderline of tractability

Tildelt: kr 59 994

One of the greatest achievements in theoretical computer science is the development of the NP-completeness theory, providing a solid and convincing mathematical foundation for the study of computationally intractable problems, that are abundant and ubiqui tous. Such problems are called NP-hard. Despite the intractability of NP-hard problems, their practical importance necessitates computational methods for finding solutions. Many approaches have been proposed, including polynomial-time approximation algori thms, randomized algorithms, and heuristic algorithms. A relatively new approach to cope with NP-hard problems is parameterized algorithms which try to bound the seemingly unavoidable combinatorial explosion into only a part of the input, the so-called pa rameter. If the parameter is small, parameterized algorithms can be very efficient. We aim at the design of efficient algorithms in particular for combinatorial problems formulated in terms of graph theory. For us, efficient algorithms are not restricted to polynomial-time algorithms only but also include the more general parameterized algorithms. The class of problems admitting this kind of algorithms is termed PT, which stands for fixed-parameter tractable. On the downside of this theory, there exist al so problem classes that are strongly supposed not to possess efficient algorithms, most notably formalized by the complexity classes W[0], W[1], W[2], ..., and resulting W-hierarchy. The main objective of the project is to determine the borderline between tractable and intractable problems. The two collaborating groups in this project from Bergen, Norway, and Trier, Germany, are among leading experts in the field of parameterized algorithms and they have been focusing on the same kind of questions from different backgrounds. Hence joining forces, the union of this expertise is expected to be extremely fruitful.


IS-DAAD-Forskerutveksl. Norge-Tyskland