It seems that by now almost everybody in our community has accepted that P≠NP holds true, although we do not have the slightest idea how to prove it. Regardless, P≠NP means that there are no polynomial time algorithms for NP-hard problems, and that super-polynomial time algorithms are the best we can hope for when dealing with exact algorithms for NP-hard problems.

Recently, there have been some fascinating activities on exact algorithms. For example, there has been a long sequence of papers on exact algorithms for 3-satisfiability. The current best algorithm for this problem is due to Iwama and Tamaki (2003) and needs roughly 1.324ⁿ time for instances with n variables. Fomin and Kratsch (September 2003) have just developed a 1.993ⁿ exact algorithm for determining the tree-width of an n-vertex graph - this is clearly not the last result on this problem. Fedin and Kulikov (2002) gave an exact 2^m/4 algorithm for the Max-Cut problem on graphs with m edges. There also has been a number of ever improving algorithms for the Vertex Cover problem; the current best is from Chen, Kanj, and Jia (2001) and it finds a Vertex Cover of size k in a graph of size n in time 1.285^k+kn .

However, many very interesting questions are still wide open and have received little if any attention. We mention just two examples here:

• Held and Karp (1962) designed a dynamic programming algorithm for the n -city traveling salesman problem with a running time of roughly 2ⁿ . This running time has not been improved in more than 40 years.
• Nesetril and Poljak (1985) observed that a simple algorithm based on matrix multiplication finds a clique of size k in an n-vertex graph in time n^0.79k . No improvement has been made since then.

More qualitatively, we ask if there are algorithms solving the satisfiability problem or the traveling salesman problem in time 2^o(n) or the clique problem in time n^o(k) . Very little is known about such lower bound questions.

The idea of fixed-parameter tractability is to approach hard algorithmic problems by isolating problem parameters that can be expected to be small in certain applications and then develop algorithms that are polynomial except for an arbitrary dependence on the parameter. More precisely, a problem is fixed-parameter tractable if its running time is f(k)p(n) , where f is an arbitrary function and p a polynomial. Since the choice of suitable parameters allows for a great flexibility, fixed-parameter algorithms have found their way into practical applications such diverse as computational biology, database systems, computational linguistics, and automated verification. The algorithmic methods developed in this area are not far from those used in the exact algorithms mentioned above. As a matter of fact, the fast algorithms for Vertex Cover have been developed in the context of fixed-parameter tractability. But beyond these algorithmic results, parameterized complexity also offers a well developed theory of intractability, and this theory may provide us with the right tools to systematically approach a theory of lower bounds for exact algorithms. For example, parameterized complexity allows us to establish exponential lower bounds on hard problems, modulo complexity assumptions. Indeed, recent work has substantiated the fact that this approach has deep links with the existence of feasible PTAS's, and limited nondeterminism; so we see the exciting emerging interplay between a number of hitherto unlinked groups of researcher.

To summarize, the area of Exact Algorithms is still in a rudimentary stage, but it is full of fascinating and difficult open problems. Fixed-parameter tractability is a branch of algorithms and complexity theory that seems very well suited to approach some of these questions. Connections between the two areas have recently evolved, ranging from very practical questions in algorithms design to the fundamental complexity theoretic problems.

The Seminar

The seminar brought together leading researchers from exact algorithms and parameterized complexity theory. If not before, it became very clear during the seminar that the areas are quickly growing together. Topics of the seminar ranged from very practical aspects of algorithm engineering for applications in computational biology to theoretical and mathematical topics such structural parameterized complexity and matroid theory. The technical program consisted of 7 invited one hour talks and 25 half hour talks. There will be a special issue of the journal Theory of Computing Systems , edited by Rod Downey, devoted to work arizing from this seminar.

The main topics of the seminar can be grouped as follows:

• Better Exact and Parameterized Algorithms
• Applications and Algorithm Engineering
• Decompositions of Graphs and Matroids and their Algorithmic Applications
• New Developments in Parameterized Complexity