Coping with the NP-hardness: Parameterized and exact algorithms

The seminal observations from the late 1960s that many computational problems did not seem to have any efficient algorithm and could therefore not be solved in practice, has continued to guide the field of algorithms and computational complexity. Several methods for dealing with NP-hard problems were developed including approximation, randomized and online algorithms and heuristic methods. All these approaches have drawbacks and disadvantages. In this same period the hardware industry has produced comput ers whose internal clock-rates are such that computational efforts taking several hours some years ago are now dealt with in milliseconds.The last few years has thus seen an emerging interest in exact solutions for NP-hard problems. With the increased sp eed of modern computers, certain hard problems can be solved effectively, and fast algorithms, even though they have exponential running times, may actually lead to practical algorithms, at least for moderate instance sizes. At the current state there is no a general theory and we have only isolated results scattered across the literature. This project aims to develop new methods and theories in the field and to study their practical usefulness. We plan to implement efficient algorithms for several probl ems motivated from practice and investigate their performance. Related NFR project 'Exact Algorithms for Hard Problems' is obtained by the applicant.